QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317187#6692. Building CompanysqzWA 0ms18388kbC++142.8kb2024-01-28 17:33:092024-01-28 17:33:12

Judging History

你现在查看的是最新测评结果

  • [2024-01-28 17:33:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18388kb
  • [2024-01-28 17:33:09]
  • 提交

answer

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

#include<queue>
#include<unordered_map>
using namespace std;
const int N = 300000;

int t[N + 5], u[N + 5], m[N + 5], k[N + 5];
vector<long long> c[N + 5], d[N + 5];
unordered_map<int, long long> cnt;
queue<int> Q;
unordered_map<int, priority_queue<pair<long long, int> > > X;

int main()
{
    int g, num = 0;
    scanf("%d", &g);
    for (int i = 1; i <= g; i++) {
        scanf("%d %d", &t[i], &u[i]);
    }
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &m[i]);
        for (int j = 1; j <= m[i]; j++) {
            int aa, bb;
            scanf("%d %d", &aa, &bb);
            X[aa].push(make_pair(-bb, i));
        }
        scanf("%d", &k[i]);
        c[i].push_back(0);
        d[i].push_back(0);
        for (int j = 1; j <= k[i]; j++) {
            int cc, dd;
            scanf("%d %d", &cc, &dd);
            c[i].push_back(cc);
            d[i].push_back(dd);
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (m[i] <= 0) ans++, Q.push(i);
    for (int i = 1; i <= g; i++) 
    {
        long long &val = cnt[t[i]];
        val += u[i];
        priority_queue<pair<long long, int> > &heap = X[t[i]];
        while (-heap.top().first <= val)
        {
            pair<long long, int> cur = heap.top();
            m[cur.second]--;
            if (m[cur.second] <= 0) {
                ans++;
                Q.push(i);
            }
            heap.pop();
        }
    }
    // printf("after\n");
    // printf("%d\n", ans);
    
    while (!Q.empty())
    {
        int i = Q.front();
        Q.pop();
        // printf("pop %d\n", i);
        for (int j = 1; j <= k[i]; j++)
        {
            long long &val = cnt[c[i][j]];
            val += d[i][j];
            priority_queue<pair<long long, int> > &heap = X[c[i][j]];
            // if (val <= 10) printf("ffff%d %d %d %d \n", j, c[i][j], val, heap.size());
            while (!heap.empty() && -heap.top().first <= val)
            {
                int nxt = heap.top().second;
                // if (m[nxt] >= 0) {
                //     printf("unlimit %d %d\n", nxt, m[nxt]);
                    // printf("%d %d %d\n", X[c[i][j]].top().first, X[c[i][j]].top().second, X[c[i][j]].size());
                // }
                m[nxt]--;
                if (m[nxt] <= 0) {
                    ans++;
                    Q.push(nxt);
                }
                heap.pop();
                // if (limit[nxt] >= 0) {
                //     printf("%d %d %d\n", X[c[i][j]].top().first, X[c[i][j]].top().second, X[c[i][j]].size());
                // }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 17876kb

input:

2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 18388kb

input:

3 610031727 590328742 816793299 18485566 654221125 47823436
10
3 610031727 224714165 816793299 491951703 654221125 593479446
1 610031727 538596643
1 610031727 551036304
3 816793299 262985484 610031727 52580932 654221125 424397787
1 654221125 889197190
3 654221125 126924193 610031727 963399336 816793...

output:

2

result:

wrong answer 1st numbers differ - expected: '10', found: '2'