| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 330745 |
2020-11-26T12:54:34 Z |
htc001 |
Plahte (COCI17_plahte) |
C++14 |
|
2000 ms |
109704 KB |
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<pii,pii> p4i;
typedef pair<pll,pll> p4l;
const int N=150005;
int n,q,nx,ny;
p4l rec[N];
p4i mrec[N];
pll qr[N];
int tp[N];
pii mqr[N];
map<long long,int> mpx,mpy;
vector<int> ope[N*3][3];
int res[N],ans[N],p[N];
vector<int> nei[N];
set<int> ex[N],st[N];
const int maxn=N*6;
int m=1;
int lson[maxn],rson[maxn],val[maxn];
void build(int pos,int x,int y){
val[pos]=-1;
if(x==y) return;
int mid=(x+y)>>1;
build(lson[pos]=++m,x,mid);
build(rson[pos]=++m,mid+1,y);
}
void pushdown(int pos){
if(val[pos]!=-1){
val[lson[pos]]=val[pos];
val[rson[pos]]=val[pos];
val[pos]=-1;
}
}
void modify(int pos,int x,int y,int l,int r,int vl){
if(x>=l&&y<=r){
val[pos]=vl;
return;
}
if(x>r||y<l) return;
int mid=(x+y)>>1;
pushdown(pos);
modify(lson[pos],x,mid,l,r,vl);
modify(rson[pos],mid+1,y,l,r,vl);
}
int query(int pos,int x,int y,int pl){
if(x==y) return max(val[pos],0);
int mid=(x+y)>>1;
pushdown(pos);
if(pl<=mid) return query(lson[pos],x,mid,pl);
else return query(rson[pos],mid+1,y,pl);
}
void dfs(int x){
res[x]=x;
int hs=-1;
for(int i=0;i<int(nei[x].size());i++){
int to=nei[x][i];
dfs(to);
if(hs==-1||ans[hs]<ans[to]) hs=to;
}
if(hs!=-1) res[x]=res[hs];
for(int i=0;i<int(nei[x].size());i++){
int to=nei[x][i];
if(to==hs) continue;
for(set<int>::iterator it=st[res[hs]].begin();it!=st[res[hs]].end();it++) st[res[x]].insert(*it);
}
for(set<int>::iterator it=ex[x].begin();it!=ex[x].end();it++) st[res[x]].insert(*it);
ans[x]=int(st[res[x]].size());
}
int main(){
// freopen("b.in","r",stdin);
// freopen("b.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
long long A,B,C,D;
scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
rec[i]=p4l(pll(A,B),pll(C,D));
mpx[A];mpx[C];
mpy[B];mpy[D];
}
for(int i=1;i<=q;i++){
long long A,B;
scanf("%lld%lld%d",&A,&B,tp+i);
qr[i]=make_pair(A,B);
mpx[A];mpy[B];
}
for(map<long long,int>::iterator it=mpx.begin();it!=mpx.end();it++) it->second=++nx;
for(map<long long,int>::iterator it=mpy.begin();it!=mpy.end();it++) it->second=++ny;
for(int i=1;i<=n;i++){
mrec[i]=p4i(pii(mpx[rec[i].first.first],mpy[rec[i].first.second]),pii(mpx[rec[i].second.first],mpy[rec[i].second.second]));
ope[mrec[i].first.first][0].push_back(i);
ope[mrec[i].second.first][2].push_back(i);
}
for(int i=1;i<=q;i++){
mqr[i]=pii(mpx[qr[i].first],mpy[qr[i].second]);
ope[mqr[i].first][1].push_back(i);
}
build(1,1,ny);
for(int i=1;i<=nx;i++){
for(int j=0;j<int(ope[i][0].size());j++){
int x=ope[i][0][j];
p[x]=query(1,1,ny,mrec[x].first.second);
nei[p[x]].push_back(x);
modify(1,1,ny,mrec[x].first.second,mrec[x].second.second,x);
}
for(int j=0;j<int(ope[i][1].size());j++){
int x=ope[i][1][j];
ex[query(1,1,ny,mqr[x].second)].insert(tp[x]);
}
for(int j=0;j<int(ope[i][2].size());j++){
int x=ope[i][2][j];
modify(1,1,ny,mrec[x].first.second,mrec[x].second.second,p[x]);
}
}
dfs(0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
/*
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 1
2 6 2
4 7 1
3 12
1 1 6 6
2 2 5 5
3 3 4 4
3 3 1
3 4 1
4 3 3
4 4 3
2 2 5
2 5 5
5 2 7
5 5 7
1 6 9
1 1 9
6 1 11
6 6 11
*/
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
82 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
plahte.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
85 | scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
92 | scanf("%lld%lld%d",&A,&B,tp+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
465 ms |
67068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1308 ms |
71932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2092 ms |
88156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2089 ms |
109704 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2101 ms |
108112 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
