| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53003 |
2018-06-27T14:11:45 Z |
hamzqq9 |
Plahte (COCI17_plahte) |
C++14 |
|
387 ms |
35044 KB |
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1050000001
#define N 80005
#define LOG 19
#define magic 100
#define KOK 350
#define EPS 0.000000000001
#define pw(x) 1ll*((1ll)<<(x))
#define PI 3.1415926535
using namespace std;
struct rect {
int a,b,c,d;
vector<int> ch;
set<int> colors;
} R[N];
struct point {
int x,y,c;
} P[N];
int n,m,cnt;
int lazy[N*4],S[N*4],ans[N],vis[N],ata[N];
vector<int> Compressed;
vector<ii> eventP;
vector<iii> eventR;
void push(int node,int bas,int son) {
if(~lazy[node]) {
S[node*2]=S[node*2+1]=lazy[node*2]=lazy[node*2+1]=lazy[node];
lazy[node]=-1;
}
}
void up(int node,int bas,int son,int x,int y,int val) {
if(x>y) return ;
if(bas>y || son<x) return ;
if(bas>=x && son<=y) {
lazy[node]=S[node]=val;
return ;
}
push(node,bas,son);
up(node*2,bas,orta,x,y,val);
up(node*2+1,orta+1,son,x,y,val);
}
int get(int node,int bas,int son,int x) {
if(x<1 || x>cnt) return 0;
if(bas==x && son==x) return S[node];
push(node,bas,son);
if(x<=orta) return get(node*2,bas,orta,x);
return get(node*2+1,orta+1,son,x);
}
void merge(set<int> &to,set<int> &from) {
for(auto x:from) {
if(to.find(x)==to.end()) to.insert(x);
}
from.clear();
}
void dfs(int node) {
//assert(!vis[node]);
vis[node]=1;
for(int go:R[node].ch) {
dfs(go);
if(sz(R[go].colors)>sz(R[node].colors)) swap(R[go].colors,R[node].colors);
merge(R[node].colors,R[go].colors);
}
ans[node]=sz(R[node].colors);
}
int main() {
#if 0
freopen("input.txt","r",stdin);
#endif
fill(lazy,lazy+N*4,-1);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d %d %d %d",&R[i].a,&R[i].b,&R[i].c,&R[i].d);
eventR.pb({{R[i].b,i},0});
eventR.pb({{R[i].d+1,i},-1});
}
for(int i=1;i<=m;i++) {
scanf("%d %d %d",&P[i].x,&P[i].y,&P[i].c);
}
sort(P+1,P+1+m,[](point x,point y) {
return x.x<y.x;
});
for(int i=1;i<=m;i++) {
eventP.pb({P[i].y,i});
}
for(int i=1;i<=m;i++) {
++cnt;
while(i+1<=m && P[i].x==P[i+1].x) P[i].x=cnt,i++;
Compressed.pb(P[i].x);
P[i].x=cnt;
}
for(int i=1;i<=n;i++) {
int x1=lower_bound(all(Compressed),R[i].a)-Compressed.begin()+1;
int x2=upper_bound(all(Compressed),R[i].c)-Compressed.begin();
R[i].a=x1;
R[i].c=x2;
}
sort(all(eventR),[](iii x,iii y) {
if(x.st.st<y.st.st) return true;
if(x.st.st>y.st.st) return false;
if(x.nd<y.nd) return true;
return false;
});
sort(all(eventP));
int last=-1;
for(int i=0;i<sz(eventR);i++) {
int id=eventR[i].st.nd;
int x1=R[id].a;
int x2=R[id].c;
while(last+1<sz(eventP) && eventR[i].st.st>eventP[last+1].st) {
last++;
// dbg(eventP[last].st);
// dbg(eventR[i].st.st);
int curR=get(1,1,cnt,P[eventP[last].nd].x);
R[curR].colors.insert(P[eventP[last].nd].c);
}
//dbg(last);
if(eventR[i].nd==0) {
int cur=get(1,1,cnt,x1);
R[cur].ch.pb(id);
ata[id]=cur;
up(1,1,cnt,x1,x2,id);
}
else {
up(1,1,cnt,x1,x2,ata[id]);
}
}
for(int i=1;i<=n;i++) {
if(!ata[i]) {
dfs(i);
}
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
plahte.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&R[i].a,&R[i].b,&R[i].c,&R[i].d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&P[i].x,&P[i].y,&P[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
12268 KB |
Output is correct |
| 2 |
Correct |
122 ms |
13856 KB |
Output is correct |
| 3 |
Correct |
10 ms |
13856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
15204 KB |
Output is correct |
| 2 |
Correct |
139 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
21588 KB |
Output is correct |
| 2 |
Correct |
212 ms |
21588 KB |
Output is correct |
| 3 |
Correct |
9 ms |
21588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
30680 KB |
Output is correct |
| 2 |
Correct |
359 ms |
30680 KB |
Output is correct |
| 3 |
Correct |
10 ms |
30680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
346 ms |
33948 KB |
Output is correct |
| 2 |
Correct |
387 ms |
35044 KB |
Output is correct |
| 3 |
Correct |
11 ms |
35044 KB |
Output is correct |
