QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#162840#7105. Pixel Artucup-team870RE 2ms8780kbC++173.7kb2023-09-03 17:07:302023-09-03 17:07:30

Judging History

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

  • [2023-09-03 17:07:30]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:8780kb
  • [2023-09-03 17:07:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
#define ilr int i,int l,int r
#define ls i<<1,l,mid
#define rs i<<1|1,mid+1,r
#define mi int mid=l+r>>1;
const int N=1e5+5;
vector<P>ask[N],del[N];
int d[N],fa[N];
map<P,int>mp;
vi fas;
int fd(int x){
    if(x==fa[x])return x;
    return fa[x]=fd(fa[x]);
}
void getqj(int l,int r){
    auto it=mp.lower_bound({l,0}); --it;
    while(it->first.first <= r){
        auto [x,y]=it->first;
        if(min(r,y)>=max(l,x))fas.push_back(fd(it->second));
        ++it;
    }
}
void slv(){
    mp.clear(); mp[{-2,-2}]=0; mp[{N,N}]=0;
    int n,m,k;cin>>n>>m>>k;
    rep(i,1,k){
        int r1,c1,r2,c2;cin>>r1>>c1>>r2>>c2;
        ask[r1].push_back({c1,c2}); del[r2+1].push_back({c1,c2});
        d[r1]+=c2-c1+1,d[r2+1]-=c2-c1+1;
    }
    ll res1=0,res2=0,cf=0;
    int cnt=0;
    rep(i,1,n){
        cf+=d[i]; res1+=cf;
        sort(ask[i].begin(),ask[i].end());
        vi vec[ask[i].size()]; vi ok(ask[i].size());
        auto get1=[&](int l,int r){
            // cout<<l<<' '<<r<<'\n';
            fas.clear(); ok[l]=r+1;
            getqj(ask[i][l].first,ask[i][r].second);
            vec[l].insert(vec[l].end(),fas.begin(),fas.end());
        };
        int l=-1,r;
        for(int j=0;j<ask[i].size();++j){
            if(j==0){l=0,r=0;continue;}
            if(ask[i][j].first!=ask[i][j-1].second+1){
                get1(l,r); l=j;
            }
            r=j;
        }
        if(l!=-1)get1(l,r);

        for(auto [c1,c2]:del[i])mp.erase({c1,c2});
        auto get2=[&](int l,int r){
            fas.clear();
            getqj(ask[i][l].first-1,ask[i][l].first-1); getqj(ask[i][r].second+1,ask[i][r].second+1);
            vec[l].insert(vec[l].end(),fas.begin(),fas.end());
            ++cnt,++res2; fa[cnt]=cnt;
            rep(k,l,r)mp[ask[i][k]]=cnt;
            vec[l].push_back(cnt); int rt=vec[l][0];
            sort(vec[l].begin(),vec[l].end());
            int pre=-1;
            for(auto v:vec[l]){
                if(v==pre)continue; //需要去重
                pre=v; assert(fa[v]==v);
                if(v!=rt)fa[v]=rt,--res2;
            }
        };
        l=-1;
        for(int j=0;j<ask[i].size();++j){
            if(j==0){l=0,r=0;continue;}
            if(ask[i][j].first!=ask[i][j-1].second+1){
                get2(l,r); l=j;
            }
            r=j;
        }
        if(l!=-1)get2(l,r);
        // for(int j=0;j<ask[i].size();++j){ 整个放在get2里面就不用再更新rt了
        //     if(!ok[j])continue;
        //     for(auto &v:vec[j])v=fd(v); //查询到的可能合并之后变了!!s
        //     ++cnt,++res2; fa[cnt]=cnt;
        //     int r=ok[j]-1;
        //     rep(k,j,r)mp[ask[i][k]]=cnt;
        //     vec[j].push_back(cnt); int rt=vec[j][0];
        //     sort(vec[j].begin(),vec[j].end());
        //     int pre=-1;
        //     for(auto v:vec[j]){
        //         if(v==pre)continue; //需要去重
        //         pre=v; 
        //         if(v!=rt)fa[v]=rt,--res2;
        //     }
        // }
        cout<<res1<<' '<<res2<<'\n';
    }
    rep(i,1,n+1)ask[i].clear(),del[i].clear(),d[i]=0;
}
signed main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}
/*
4 5 6
1 1 2 1
1 4 1 4
1 5 3 5
2 2 3 2
2 3 3 3
4 3 4 5

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

3 3 3
1 1 2 1
2 2 2 2
1 3 3 3

3 4 4
1 2 1 2
2 1 3 1
2 2 3 2
2 3 3 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
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Dangerous Syscalls

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: