| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 667796 |
2022-12-02T04:18:18 Z |
slo |
Plahte (COCI17_plahte) |
C++17 |
|
1535 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-----------------*/
struct Point{ ll x, y; int recId;};
struct Rec{ Point p, q; int id;};
struct Shot{ ll x, y; int color;};
struct SegTree{
int n;
vector<set<pii>> seg, lazy;
SegTree(int _n=0){
n=_n;
seg.assign(4*n+7,set<pii>());
lazy.assign(4*n+7,set<pii>());
}
void down(int i, int l, int r){
if(l<r){
for(pii cmd:lazy[i]){
int k=i<<1;
auto it=seg[k].find(cmd);
if(it==seg[k].end()) seg[k].ins(cmd);
else seg[k].erase(it);
it=seg[k+1].find(cmd);
if(it==seg[k+1].end()) seg[k+1].ins(cmd);
else seg[k+1].erase(it);
it=lazy[k].find(cmd);
if(it==lazy[k].end()) lazy[k].ins(cmd);
else lazy[k].erase(it);
it=lazy[k+1].find(cmd);
if(it==lazy[k+1].end()) lazy[k+1].ins(cmd);
else lazy[k+1].erase(it);
}
lazy[i].clear();
}
}
void upd(int i, int l, int r, int u, int v, pii cmd){
if(v<l || r<u) return;
if(u<=l && r<=v){
auto it=seg[i].find(cmd);
if(it==seg[i].end()) seg[i].ins(cmd);
else seg[i].erase(it);
it=lazy[i].find(cmd);
if(it==lazy[i].end()) lazy[i].ins(cmd);
else lazy[i].erase(it);
return;
}
down(i,l,r);
int m=(l+r)>>1, k=i<<1;
upd(k,l,m,u,v,cmd);
upd(k+1,m+1,r,u,v,cmd);
}
void upd(int u, int v, pii cmd){
upd(1,0,n,u,v,cmd);
}
int calc(int i, int l, int r, int pos){
if(pos<l || r<pos) return -1;
down(i,l,r);
if(l==r){
if(seg[i].empty()) return -1;
return seg[i].rbegin()->se;
}
int m=(l+r)>>1, k=i<<1;
return max(calc(k,l,m,pos),calc(k+1,m+1,r,pos));
}
int calc(int pos){
return calc(1,0,n,pos);
}
};
const int N=1e5+7;
int n, m;
vector<Rec> rec;
vector<Point> P;
vi adj[N];
set<int> unqCol[N];
int timer;
int t[N], par[N];
vi yVal;
bool operator ==(const Point& p, const Point& q){
return mp(p.x,p.y)==mp(q.x,q.y);
}
bool operator <(const Point& p, const Point& q){
if(p.x==q.x){
if(p.recId<0 && q.recId<0)
return p.y<q.y;
if(p.recId<0)
return q==rec[q.recId].q;
if(q.recId<0)
return p==rec[p.recId].p;
return p.y<q.y;
}
return p.x<q.x;
}
int getId(const int& y){
return lower_bound(all(yVal),y)-yVal.begin();
}
void makeTree(){
sort(all(P));
sort(all(yVal));
yVal.resize(unique(all(yVal))-yVal.begin());
rep(i,n) par[i]=i;
timer=0;
set<Point> active;
SegTree st(sz(yVal));
// st.upd(getId(rec[0].p.y),getId(rec[0].q.y),mp(0,0));
// cout<<st.calc(getId(3));
for(Point p:P)
if(p.recId<0){
int tmp=st.calc(getId(p.y));
if(tmp!=-1)
unqCol[tmp].ins(-p.recId);
}
else{
auto it=active.find(rec[p.recId].p);
if(it==active.end()){ // add
t[p.recId]=timer++;
st.upd(getId(rec[p.recId].p.y),getId(rec[p.recId].q.y),mp(t[p.recId],p.recId));
auto pos=active.ins(p).fi;
if(pos!=active.begin()){
pos--;
adj[pos->recId].pb(p.recId);
par[p.recId]=(pos->recId);
}
}
else{ // remove
st.upd(getId(rec[p.recId].p.y),getId(rec[p.recId].q.y),mp(t[p.recId],p.recId));
active.erase(it);
}
}
}
void dfs(int u){
int mxV=-1;
for(int v:adj[u]){
dfs(v);
if(mxV==-1 || sz(unqCol[mxV])<sz(unqCol[v])) mxV=v;
}
if(mxV!=-1){
set<int> cur=unqCol[mxV];
for(int c:unqCol[u]) cur.ins(c);
for(int v:adj[u]) if(v!=mxV)
for(int c:unqCol[v]) cur.ins(c);
unqCol[u]=cur;
}
}
void read(){
cin>>n>>m;
rep(i,n){
Rec r;
cin>>r.p.x>>r.p.y>>r.q.x>>r.q.y;
r.id=r.p.recId=r.q.recId=i;
rec.pb(r), P.pb(r.p), P.pb(r.q);
yVal.pb(r.p.y), yVal.pb(r.q.y);
}
rep(i,m){
Point p; cin>>p.x>>p.y>>p.recId;
p.recId=-p.recId;
P.pb(p), yVal.pb(p.y);
}
}
void solve(){
makeTree();
rep(i,n) if(par[i]==i) dfs(i);
rep(i,n) cout<<sz(unqCol[i])<<'\n';
}
int main(){
fastIO;
read();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1432 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1535 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1510 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1451 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1442 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
