| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 499314 |
2021-12-28T02:17:22 Z |
julian33 |
Plahte (COCI17_plahte) |
C++14 |
|
1774 ms |
182508 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef LOCAL
const int mxN=105;
#else
const int mxN=3e5+5; //make sure this is right
#endif
const int mod=1e9+7;
struct RANK{
vector<int> all;
int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;}
void add(int x){all.pb(x);}
void fix(){
sort(all.begin(),all.end());
all.resize(unique(all.begin(),all.end())-all.begin());
}
} rnk;
struct guy{
int a,b,c;
bool operator<(const guy &o) const{
return a<o.a;
}
};
set<guy> st[4*mxN];
void update(int v,int l,int r,int ind,guy val,int t){
if(l>ind || r<ind) return;
if(t) st[v].insert(val);
else st[v].erase(val);
if(l==r) return;
int m=(l+r)>>1;
update(v<<1,l,m,ind,val,t);
update(v<<1|1,m+1,r,ind,val,t);
}
guy query(int v,int l,int r,int lq,int rq,int lo,int hi){
if(lq>rq) return {-1,-1,-1};
if(l>=lq && r<=rq){
if(!sz(st[v])) return {-1,-1,-1};
if(st[v].rbegin()->a<lo) return {-1,-1,-1};
if(st[v].begin()->a>hi) return {-1,-1,-1};
return *st[v].lower_bound((guy){lo,-1,-1});
}
int m=(l+r)>>1;
return max(query(v<<1,l,m,lq,min(rq,m),lo,hi),query(v<<1|1,m+1,r,max(lq,m+1),rq,lo,hi));
}
struct rect{
ll a,b,c,d,i;
};
struct paint{
int x,y,k;
};
vector<int> graph[mxN];
set<int> col[mxN];
int ans[mxN];
void dfs(int at){
for(int &i:graph[at]){
dfs(i);
if(sz(col[i])>sz(col[at])) swap(col[i],col[at]);
for(int j:col[i])
col[at].insert(j);
col[i].clear();
}
ans[at]=sz(col[at]);
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,m; cin>>n>>m;
vector<rect> all,ori;
vector<paint> off;
for(int i=0;i<n;i++){
int a,b,c,d; cin>>a>>b>>c>>d;
rnk.add(a); rnk.add(c);
all.pb({a,b,c,d,i});
ori.pb({a,b,c,d,i});
}
for(int i=0;i<m;i++){
int x,y,k; cin>>x>>y>>k;
rnk.add(x);
off.pb({x,y,k});
}
rnk.fix();
sort(all.begin(),all.end(),[&](auto x,auto y){return (x.c-x.a)*(x.d-x.b)<(y.c-y.a)*(y.d-y.b);});
int N=sz(rnk.all);
// assert(sz(rnk.all)<mxN);
// deb(sz(rnk.all));
for(auto &[a,b,c,d,i]:all){
a=rnk.get(a);
c=rnk.get(c);
guy res;
while(1){
res=query(1,1,N,a,c,b,d);
if(res.a==-1) break;
// deb(res.first,res.second);
graph[min(i,(ll)res.b)].pb(max(i,(ll)res.b));
update(1,1,N,rnk.get(ori[res.b].a),res,0);
}
update(1,1,N,a,{(int)b,(int)i,-1},1);
}
for(int i=1;i<=4*N;i++)
st[i].clear();
int c=0;
for(auto &[x,y,k]:off){
x=rnk.get(x);
update(1,1,N,x,{y,k,c},1);
c++;
}
sort(all.begin(),all.end(),[&](auto x,auto y){return x.i>y.i;});
for(auto &[a,b,c,d,i]:all){
guy res;
// deb(a,b,c,d,i);
while(1){
res=query(1,1,N,a,c,b,d);
if(res.a==-1) break;
// deb(res.first,res.second);
col[i].insert(res.b);
int x=off[res.c].x;
update(1,1,N,x,res,0);
}
}
memset(ans,-1,sizeof(ans));
for(int i=0;i<n;i++){
if(ans[i]==-1) dfs(i);
cout<<ans[i]<<"\n";
}
}
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:128:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
128 | for(auto &[a,b,c,d,i]:all){
| ^
plahte.cpp:144:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
144 | for(auto &[x,y,k]:off){
| ^
plahte.cpp:150:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
150 | for(auto &[a,b,c,d,i]:all){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
493 ms |
118916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
525 ms |
115348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
929 ms |
142004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1690 ms |
182508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1774 ms |
182492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
