QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#165422 | #7105. Pixel Art | ucup-team1359 | AC ✓ | 345ms | 27568kb | C++14 | 3.5kb | 2023-09-05 17:59:54 | 2023-09-05 17:59:54 |
Judging History
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