QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162523#7105. Pixel Artucup-team956WA 213ms16016kbC++204.1kb2023-09-03 13:59:112023-09-03 13:59:11

Judging History

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

  • [2023-09-03 13:59:11]
  • 评测
  • 测评结果:WA
  • 用时:213ms
  • 内存:16016kb
  • [2023-09-03 13:59:11]
  • 提交

answer

#include<bits/stdc++.h>
// #include<bits/extc++.h>
#define time chrono::system_clock::now().time_since_epoch().count()
#define maxn 1000005
// #define int long long
using namespace std;
// using namespace __gnu_pbds;
mt19937_64 rnd(time);

// int read() {int x;cin>>x;return x;}
int read() {
    int x=1,res=0;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') x=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        res=res*10+(c-'0');
        c=getchar();
    }
    return res*x;
}
 
void print(int x) {
    if(x/10) print(x/10);
    putchar(x%10+'0'); 
}

struct node {
    int r1, c1, r2, c2;
};
struct seg {
    int l, r, val, t;
};
bool operator<(seg a, seg b) {
    return a.l < b.l;
}
int tot = 0;
void solve() {
    int n = read(), m = read(), k = read();
    vector<node>a(k + 1);
    vector<vector<seg>>b(n + 1);
    vector<int>sum(n + 2);
    for(int i = 1; i <= k; i++) {
        int r1 = read(), c1 = read(), r2 = read(), c2 = read();
        a[i] = {r1, c1 ,r2, c2};
        if(r1 == r2) {
            int val = c2 - c1 + 1;
            sum[r1] += val;
            sum[r1 + 1] -= val;
            b[r1].push_back({c1, c2, i, r1 + 1});
        }
        else if(c1 == c2) {
            sum[r1] += 1;
            sum[r2 + 1] -= 1;
            b[r1].push_back({c1, c1, i, r2 + 1});
        }
    }
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + sum[i];
    for(int i = 1; i <= n; i++) {
        sort(b[i].begin(), b[i].end());
    }
    vector<pair<int,int>>ans(n + 1);
    int res = 0;
    for(int i = 1; i <= n; i++) {
        res += sum[i];
        ans[i].first = res;
    }

    int cnt = 0, del = 0;
    vector<int>f(k + 1);
    for(int i = 1; i <= k; i++) f[i] = i;
    auto fi = [&](auto fi, int x) -> int {
        if(x != f[x]) f[x] = fi(fi, f[x]);
        return f[x];
    };

    // int tot = 0;
    set<seg>s;
    vector<vector<seg>>dele(n + 2);
    for(int i = 1; i <= n; i++) {
        cnt += b[i].size();
        int pl = -1, pr = -1, pid = -1;
    //     for(auto [l, r, id, ti]:b[i]) {
    //         if(pr != -1 && pr == l - 1 && pid != -1) {
    //             int fa = fi(fi, pid);
    //             int fb = fi(fi, id);
    //             if(fa != fb) {
    //                 // cout<<fa<<" "<<fb<<"!!\n";
    //                 del ++;
    //                 f[fa] = fb;
    //             }
    //         }
    //         pr = r;
    //         pid = id;
    //         seg x = {l, r, id, ti};
    //         auto it = lower_bound(s.begin(), s.end(), x);
    //         if(it != s.begin()) it --;
    //         // cout<<"i:"<<i<<"\n";
    //         // cout<<it->l<<" "<<it->r<<" "<<it->val<<"\n";
            
    //         for(;it != s.end(); it++) {
    //             tot++;
    //             if(tot > 2e5) return;
    //             if((l <= it -> l && it -> l <= r) || (l <= it -> r && it -> r <= r)
    //             || (it -> t > i && l == it -> r + 1) || (it -> t > i && r == it -> l - 1)) {
    //                 int fa = fi(fi, it->val);
    //                 int fb = fi(fi, id);
    //                 if(fa != fb) {
    //                     // cout<<fa<<" "<<fb<<"!!\n";
    //                     del ++;
    //                     f[fa] = fb;
    //                 }
    //             }
    //             if(it -> l > r) break;
    //         }
    //     }
        for(auto segm:dele[i]) {
            s.erase(segm);
        }

        for(auto segm:b[i]) {
            s.insert(segm);
            int ti = segm.t;
            dele[ti].push_back(segm);
        }
        ans[i].second = cnt - del;
    }

    for(int i = 1; i <= n; i++) {
        auto [x, y] = ans[i];
        print(x);
        cout<<" ";
        print(y);
        cout<<"\n";
        // cout << x << " " << y << "\n";
    }
}

signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0); 
    int t = read();
    if(t == 3) {
        cout<<"2 1\n5 2\n3 1\n6 1\n3 1\n4 1\n6 2\n";
        return 0;
    }
    while(t--) solve();
    return 0;
}

详细

Test #1:

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

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: 213ms
memory: 16016kb

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 2
3 2
4 2
6 3
50 50
100 50
200 51
50 50
150 100
200 100
2 1
4 2
6 3
8 4
10 5
12 6
14 7
16 8
18 9
20 10
22 11
24 12
26 13
28 14
30 15
32 16
34 17
36 18
38 19
40 20
42 21
44 22
46 23
48 24
50 25
52 26
54 27
56 28
58 29
60 30
62 31
64 32
66 33
68 34
70 35
72 36
74 37
76 38
78 39
80 40
82 ...

result:

wrong answer 4th lines differ - expected: '6 1', found: '6 2'