QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165422#7105. Pixel Artucup-team1359AC ✓345ms27568kbC++143.5kb2023-09-05 17:59:542023-09-05 17:59:54

Judging History

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

  • [2023-09-05 17:59:54]
  • 评测
  • 测评结果:AC
  • 用时:345ms
  • 内存:27568kb
  • [2023-09-05 17:59:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int T,n,m,k,r1[105000],c1[105000],r2[105000],c2[105000];
namespace dsu {
    int p[105000],sz;
    void make_set(int n) {
        sz=n;
        for (int i=1;i<=n;i++) p[i]=i;
    }
    int find_set(int x) {
        if (p[x]==x) return x;
        return p[x]=find_set(p[x]);
    }
    void union_set(int x,int y) {
        x=find_set(x);
        y=find_set(y);
        if (x==y) return;
        sz--;
        p[x]=y;
    }
}
namespace fen {
    int sz;
    long long pre[105000];
    void init(int n) {
        sz=n;
        for (int i=1;i<=n;i++) pre[i]=0;
    }
    void update(int x,int y) {
        while (x<=sz) {
            pre[x]+=y;
            x+=(x&(-x));
        }
    }
    long long getsum(int x) {
        long long res=0;
        while (x) {
            res+=pre[x];
            x-=(x&(-x));
        }
        return res;
    }
}
long long ans1[105000];
vector<long long> pln[105000],pcol[105000];
vector<PII> upds[105000];
int findid(int x,int y) {
    auto tmp1=upper_bound(pln[x].begin(),pln[x].end(),1000000ll*y+999999ll)-pln[x].begin(),tmp2=upper_bound(pcol[y].begin(),pcol[y].end(),1000000ll*x+999999ll)-pcol[y].begin();
    if (tmp1%2==1) {
        return pln[x][tmp1-1]%1000000;
    } else if (tmp2%2==1) {
        return pcol[y][tmp2-1]%1000000;
    } else return 0;
}
int precol[105000];
int main() {
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d%d",&n,&m,&k);
        dsu::make_set(k);
        fen::init(n+5);
        for (int i=1;i<=k;i++) {
            scanf("%d%d%d%d",&r1[i],&c1[i],&r2[i],&c2[i]);
            if (r1[i]==r2[i]) {
                fen::update(r1[i],c2[i]-c1[i]+1);
                fen::update(r1[i]+1,-(c2[i]-c1[i]+1));
                pln[r1[i]].push_back(1000000ll*c1[i]+i);
                pln[r1[i]].push_back(1000000ll*(c2[i]+1)+i);
            } else {
                fen::update(r1[i],1);
                fen::update(r2[i]+1,-1);
                pcol[c1[i]].push_back(1000000ll*r1[i]+i);
                pcol[c1[i]].push_back(1000000ll*(r2[i]+1)+i);
            }
            precol[r1[i]]++;
        }
        for (int i=2;i<=n;i++) precol[i]+=precol[i-1];
        for (int i=1;i<=n;i++) sort(pln[i].begin(),pln[i].end());
        for (int i=1;i<=k;i++) sort(pcol[c1[i]].begin(),pcol[c1[i]].end());
        for (int i=1;i<=n;i++) ans1[i]=fen::getsum(i)+ans1[i-1];
        for (int i=1;i<=k;i++) {
            int a=findid(r1[i],c1[i]-1),b=findid(r1[i],c1[i]+1),c=findid(r1[i]-1,c1[i]),d=findid(r1[i]+1,c1[i]);
            if (a>0) upds[r1[i]].push_back({a,i});
            if (b>0) upds[r1[i]].push_back({b,i});
            if (c>0) upds[r1[i]].push_back({c,i});
            if (d>0) upds[r1[i]+1].push_back({d,i});
            a=findid(r2[i],c2[i]-1),b=findid(r2[i],c2[i]+1),c=findid(r2[i]-1,c2[i]),d=findid(r2[i]+1,c2[i]);
            if (a>0) upds[r2[i]].push_back({a,i});
            if (b>0) upds[r2[i]].push_back({b,i});
            if (c>0) upds[r2[i]].push_back({c,i});
            if (d>0) upds[r2[i]+1].push_back({d,i});
        }
        for (int i=1;i<=n;i++) {
            for (auto cur:upds[i]) dsu::union_set(cur.first,cur.second);
            printf("%lld %d\n",ans1[i],dsu::sz+precol[i]-k);
        }
        for (int i=1;i<=n;i++) {
            upds[i].clear();
            pln[i].clear();
            precol[i]=0;
        }
        for (int i=1;i<=k;i++) pcol[c1[i]].clear();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 345ms
memory: 27568kb

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:

ok 355756 lines

Extra Test:

score: 0
Extra Test Passed