震惊!!!某蒟蒻居然找不到自己RE的原因QAQ
查看原帖
震惊!!!某蒟蒻居然找不到自己RE的原因QAQ
54713
icefake楼主2020/9/19 00:13

第四个和第十二个点RE了awaawa

#include<bits/stdc++.h>
#define int long long

using namespace std;

priority_queue <int> Q;
priority_queue <int, vector<int>, greater<int> > q;
const int maxn = 100000010;
int n, ans = 0, k = 1, tem, tot = 0;
struct fn {
    int val, time;
}f[maxn];

int read(){
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}

bool cmp(fn x, fn y)
{
    return x.time <= y.time;
}

signed main()
{
    #ifndef ONLINE_JUDGE
  	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
    #endif  

    n = read();
    for(int i = 1; i <= n; i ++) f[i].time = read(), f[i].val = read();
    sort(f + 1, f + n + 1, cmp);
    while(k <= n) {
        tem = f[k].time;
        while(f[k].time == tem) {
            Q.push(f[k].val);
            k ++;
        }
        while(!Q.empty()) { 
            if(tot == tem) {
                if(Q.top() > q.top()) {
                    ans += Q.top() - q.top();
                    q.pop(); q.push(Q.top()); Q.pop();
                }
                else break;
            }
            else {
                ans += Q.top(); q.push(Q.top()); Q.pop();
                tot ++;
            }
        }
        while(!Q.empty()) Q.pop();
    }   
    printf("%lld", ans);
    return 0;
}
2020/9/19 00:13
加载中...