QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#166085#7105. Pixel Artucup-team045WA 210ms22016kbC++203.4kb2023-09-06 00:55:112023-09-06 00:55:12

Judging History

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

  • [2023-09-06 00:55:12]
  • 评测
  • 测评结果:WA
  • 用时:210ms
  • 内存:22016kb
  • [2023-09-06 00:55:11]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
using LL = long long;
int p[1000005];

int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}

bool merge(int x, int y){
    x = find(x), y = find(y);
    if (x == y) return false;
    p[x] = y;
    return true;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    vector<int> id(1000005), c(1000005);
    int T;
    cin >> T;
    while(T--){
        int n, m, k;
        cin >> n >> m >> k;
        vector<vector<pair<int, int> > > pos(n + 2);
        vector<vector<int> > add(n + 2), del(n + 2);
        vector<LL> s(n + 2);
        for(int i = 0; i < k; i++){
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 == x2){
                pos[x1].push_back({y1, y2});
                s[x1] += y2 - y1 + 1;
                s[x1 + 1] -= y2 - y1 + 1;
            }
            else{
                add[x1].push_back(y1);
                del[x2 + 1].push_back(y1);
                s[x1] += 1;
                s[x2 + 1] -= 1;
            }
        }
        for(int i = 1; i <= n; i++) s[i] += s[i - 1];
        for(int i = 1; i <= n; i++) s[i] += s[i - 1];
        int conn = 0, idx = 0;
        vector<array<int, 3> > last;
        
        for(int i = 1; i <= n; i++){
            for(auto x : add[i]){
                ++c[x];
                if (!id[x]){
                    id[x] = ++idx;
                    conn += 1;
                    p[idx] = idx;
                }
            }
            vector<pair<int, int> > last2;
            for(auto x : del[i]){
                last2.push_back({x, id[x]});
                if (--c[x] == 0){
                    id[x] = 0;
                }
            }
            for(auto x : add[i]){
                if (id[x - 1]) conn -= merge(id[x], id[x - 1]);
                if (id[x + 1]) conn -= merge(id[x], id[x + 1]);
            }
            sort(last2.begin(), last2.end());
            sort(pos[i].begin(), pos[i].end());
            int j = -1, k = -1;
            vector<array<int, 3> > cur;
            for(auto [l, r] : pos[i]){
                ++idx;
                p[idx] = idx;
                conn += 1;
                if (j >= 0 && j < last.size()){
                    auto [L, R, id] = last[j];
                    if (max(L, l) <= min(R, r)){
                        conn -= merge(idx, id);
                    }
                }
                while(j + 1 < last.size() && last[j + 1][0] <= r){
                    auto [L, R, id] = last[++j];
                    if (max(L, l) <= min(R, r)){
                        conn -= merge(idx, id);
                    }
                }
                while(k + 1 < last2.size() && last2[k + 1].first <= r){
                    auto [x, id] = last2[++k];
                    if (x >= l && x <= r){
                        conn -= merge(idx, id);
                    }
                }
                if (id[l - 1]) conn -= merge(idx, id[l - 1]);
                if (id[r + 1]) conn -= merge(idx, id[r + 1]);
                cur.push_back({l, r, idx});
            }
            last.swap(cur);
            cout << s[i] << ' ' << conn << '\n';
        }
    }

}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10824kb

input:

3
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3

output:

2 1
5 2
3 1
6 1
3 1
4 1
6 2

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 210ms
memory: 22016kb

input:

2130
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3
3 100 51
1 2 2 2
1 4 2 4
1 6 2 6
1 8 2 8
1 10 2 10
1 12 2 12
1 14 2 14
1 16 2 16
1 18 2 18
1 20 2 20
1 22 2 22
1 24 2 24
1 26 2 26
1 28 2 28
1 30 2 30
1 32 2 32
1 34 2 34
1 36 2 36
1 38 2 38
1 40 2 40
1 42 2 42
1 44 2 44
...

output:

2 1
5 2
3 1
6 1
3 1
4 1
6 2
50 50
100 50
200 1
50 50
150 1
200 1
2 1
4 1
6 1
8 1
10 1
12 1
14 1
16 1
18 1
20 1
22 1
24 1
26 1
28 1
30 1
32 1
34 1
36 1
38 1
40 1
42 1
44 1
46 1
48 1
50 1
52 1
54 1
56 1
58 1
60 1
62 1
64 1
66 1
68 1
70 1
72 1
74 1
76 1
78 1
80 1
82 1
84 1
86 1
88 1
90 1
92 1
94 1
96 1...

result:

wrong answer 115th lines differ - expected: '10 10', found: '10 5'