| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 667956 |
2022-12-02T12:12:45 Z |
slo |
Plahte (COCI17_plahte) |
C++14 |
|
385 ms |
524288 KB |
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define Pi acos(-1.0)
#define mp make_pair
#define ins insert
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define sz(a) (a.size())
#define all(a) a.begin(), a.end()
#define numZeroBitStart(x) (__builtin_clz(x))
#define numZeroBitEnd(x) (__builtin_ctz(x))
#define numOneBit(x) (__builtin_popcount(x))
#define parityOfNumOneBit(x) (__builtin_parity(x))
typedef long long ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pill;
typedef pair<ll,int> plli;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps=1e-9;
if(x+eps<y){
x=y; return true;
}
return false;
}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps=1e-9;
if(x>y+eps){
x=y; return true;
}
return false;
}
/*-----------------MAIN PROGRAM-----------------*/
const int N=1e5+7;
struct Rec{
int x1=0, y1=0, x2=0, y2=0;
};
struct Ball{
int x, y, k;
};
struct SegTree{
int n;
vector<stack<pii> > seg;
SegTree(int _n=0){
n=_n;
seg.assign(4*n+7,stack<pii>());
}
void add(int i, int l, int r, int u, int v, pii val){
if(v<l || r<u) return;
if(u<=l && r<=v){
seg[i].push(val);
return;
}
int m=(l+r)>>1, k=i<<1;
add(k,l,m,u,v,val);
add(k+1,m+1,r,u,v,val);
}
void add(int l, int r, pii val){
add(1,0,n-1,l,r,val);
}
void remv(int i, int l, int r, int u, int v){
if(v<l || r<u) return;
if(u<=l && r<=v){
seg[i].pop();
return;
}
int m=(l+r)>>1, k=i<<1;
remv(k,l,m,u,v);
remv(k+1,m+1,r,u,v);
}
void remv(int l, int r){
remv(1,0,n-1,l,r);
}
int calc(int pos){
int i=1, l=0, r=n-1, latest=-1, res=-1;
while(l<=r){
if(!seg[i].empty() && maximize(latest,seg[i].top().fi))
res=seg[i].top().se;
if(l==r) break;
int m=(l+r)>>1;
if(pos<=m){
i<<=1;
r=m;
}
else{
i=(i<<1)+1;
l=m+1;
}
}
return res;
}
};
int n, m;
Rec rec[N];
Ball ball[N];
vi adj[N];
int par[N], ans[N];
set<int> color[N];
void read(){
cin>>n>>m;
rep(i,n)
cin>>rec[i].x1>>rec[i].y1>>rec[i].x2>>rec[i].y2;
rep(i,m)
cin>>ball[i].x>>ball[i].y>>ball[i].k;
}
void hashing(){
vi v;
rep(i,n) v.pb(rec[i].y1), v.pb(rec[i].y2);
rep(i,m) v.pb(ball[i].y);
sort(all(v));
v.resize(unique(all(v))-v.begin());
rep(i,n){
rec[i].y1=lower_bound(all(v),rec[i].y1)-v.begin();
rec[i].y2=lower_bound(all(v),rec[i].y2)-v.begin();
}
rep(i,m)
ball[i].y=lower_bound(all(v),ball[i].y)-v.begin();
}
void sweep(){
vector<pair<pii,pii> > evt;
rep(i,n){
evt.pb(mp(mp(rec[i].x1,i+1),mp(rec[i].y1,rec[i].y2)));
evt.pb(mp(mp(rec[i].x2+1,-(i+1)),mp(rec[i].y1,rec[i].y2)));
}
rep(i,m)
evt.pb(mp(mp(ball[i].x,N),mp(ball[i].y,i)));
sort(all(evt));
rep(i,n) par[i]=i;
SegTree ds(2*n+m);
rep(i,sz(evt))
if(evt[i].fi.se==N){ // paintball
int recId=ds.calc(evt[i].se.fi);
if(recId!=-1)
color[recId].ins(ball[evt[i].se.se].k);
}
else if(evt[i].fi.se>0){ // add rec
int curRecId=evt[i].fi.se-1;
int recId=ds.calc(evt[i].se.se);
if(recId!=-1){
par[curRecId]=recId;
adj[recId].pb(curRecId);
//cout<<recId+1<<' '<<curRecId+1<<'\n';
}
ds.add(evt[i].se.fi,evt[i].se.se,mp(i,curRecId));
}
else // remove rec
ds.remv(evt[i].se.fi,evt[i].se.se);
}
void mergeSet(int u, int v){
if(sz(color[u])<sz(color[v]))
swap(color[u],color[v]);
for(int c:color[v]) color[u].ins(c);
}
void dfs(int u){
for(int v:adj[u]){
dfs(v);
mergeSet(u,v);
}
ans[u]=sz(color[u]);
}
void solve(){
rep(i,n) if(par[i]==i) dfs(i);
rep(i,n) cout<<ans[i]<<'\n';
}
int main(){
fastIO;
read();
hashing();
sweep();
solve();
return 0;
}
Compilation message
plahte.cpp: In function 'void sweep()':
plahte.cpp:5:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forw(i,l,r) for(int i=l; i<r; i++)
| ^
plahte.cpp:8:18: note: in expansion of macro 'forw'
8 | #define rep(i,n) forw(i,0,n)
| ^~~~
plahte.cpp:160:5: note: in expansion of macro 'rep'
160 | rep(i,sz(evt))
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
184 ms |
212852 KB |
Output is correct |
| 2 |
Correct |
198 ms |
212372 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
254088 KB |
Output is correct |
| 2 |
Correct |
229 ms |
253396 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
384 ms |
419972 KB |
Output is correct |
| 2 |
Correct |
385 ms |
417048 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
329 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
337 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
