| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261249 |
2020-08-11T15:24:48 Z |
mhy908 |
Sweeping (JOI20_sweeping) |
C++14 |
|
8010 ms |
751112 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
pair<pii, int> rng[1500010];
int n, m, q, re;
struct SWP_SEG{
struct NODE{
NODE *lc, *rc;
NODE(){lc=rc=0;}
map<int, vector<int> > l, r;
vector<int> lnum, rnum, rv, ch;
struct INC_DSU{
vector<int> par;
void ins(){int sz=par.size(); par.eb(sz);}
int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}ufl, ufr;
pii get_range(int num){
int ul=ufl.findpar(num);
int ur=ufr.findpar(num);
return mp(lnum[ul], rnum[ur]);
}
void ins(int s, int e, pii rn, int num){
rng[num]=mp(mp(s, e), lnum.size());
rv.eb(num);
ufl.ins(); ufr.ins();
lnum.eb(rn.F); rnum.eb(rn.S); ch.eb(0);
if(l[rn.F].size())ufl.mergepar(rng[num].S, l[rn.F].back());
if(r[rn.S].size())ufr.mergepar(rng[num].S, r[rn.S].back());
l[rn.F].eb(rng[num].S); r[rn.S].eb(rng[num].S);
}
}*rt;
SWP_SEG(){rt=new NODE();}
pii query(NODE *nd, int s, int e, int num){
if(s==rng[num].F.F&&e==rng[num].F.S)return nd->get_range(rng[num].S);
if(rng[num].F.S<=(s+e)/2)return query(nd->lc, s, (s+e)/2, num);
return query(nd->rc, (s+e)/2+1, e, num);
}
void overkill_lft(NODE *nd, int s, int e, int num){
vector<pair<pii, int> > vc;
auto it=nd->r.end();
while(it!=nd->r.begin()){
it--;
if(it->F<num){
it++;
break;
}
for(auto i:it->S){
if(nd->ch[i])continue;
nd->ch[i]=1;
vc.eb(mp(num, it->F), i);
}
}
nd->r.erase(it, nd->r.end());
if(vc.size()==0)return;
if(!nd->rc)nd->rc=new NODE();
for(auto i:vc)upd_ins(nd->rc, (s+e)/2+1, e, i.F, nd->rv[i.S]);
}
void overkill_rgt(NODE *nd, int s, int e, int num){
vector<pair<pii, int> > vc;
auto it=nd->l.begin();
while(it!=nd->l.end()){
if(it->F>num)break;
for(auto i:it->S){
if(nd->ch[i])continue;
nd->ch[i]=1;
vc.eb(mp(it->F, num), i);
}
it++;
}
nd->l.erase(nd->l.begin(), it);
if(vc.size()==0)return;
if(!nd->lc)nd->lc=new NODE();
for(auto i:vc)upd_ins(nd->lc, s, (s+e)/2, i.F, nd->rv[i.S]);
}
void push_lft(NODE *nd, int s, int e, int num){
if(nd->l.size()==0)return;
if(nd->l.begin()->F>num)return;
auto it=nd->l.begin();
auto it2=nd->l.begin();
it2++;
while(it2!=nd->l.end()){
if(it2->F>num)break;
if(it->S.size()>it2->S.size())swap(it->S, it2->S);
for(auto i:it->S){
nd->ufl.mergepar(i, it2->S.back());
it2->S.eb(i);
}
it++; it2++;
}
nd->lnum[nd->ufl.findpar(it->S.back())]=num;
swap(it->S, nd->l[num]);
nd->l.erase(nd->l.begin(), nd->l.find(num));
}
void push_rgt(NODE *nd, int s, int e, int num){
if(nd->r.size()==0)return;
if(nd->r.rbegin()->F<num)return;
auto it=nd->r.end();
auto it2=nd->r.end();
it--;
it2--;
if(it2!=nd->r.begin())it2--;
while(it!=nd->r.begin()){
if(it2->F<num)break;
if(it->S.size()>it2->S.size())swap(it->S, it2->S);
for(auto i:it->S){
nd->ufr.mergepar(i, it2->S.back());
it2->S.eb(i);
}
it--; it2--;
}
nd->rnum[nd->ufr.findpar(it->S.back())]=num;
swap(it->S, nd->r[num]);
nd->r.erase(++(nd->r.find(num)), nd->r.end());
}
void upd_ins(NODE *nd, int s, int e, pii rn, int num){
int mid=(s+e)/2;
if((rn.F<=mid&&mid<rn.S)||s==e){
nd->ins(s, e, rn, num);
return;
}
if(rn.S<=mid){
if(!nd->lc)nd->lc=new NODE();
upd_ins(nd->lc, s, (s+e)/2, rn, num);
}
else{
if(!nd->rc)nd->rc=new NODE();
upd_ins(nd->rc, (s+e)/2+1, e, rn, num);
}
}
void upd_swpl(NODE *nd, int s, int e, int num){
if(s==e)return;
int mid=(s+e)/2;
if(num>mid){
overkill_lft(nd, s, e, num);
if(nd->rc)upd_swpl(nd->rc, (s+e)/2+1, e, num);
}
else{
push_lft(nd, s, e, num);
if(nd->lc)upd_swpl(nd->lc, s, (s+e)/2, num);
}
}
void upd_swpr(NODE *nd, int s, int e, int num){
if(s==e)return;
int mid=(s+e)/2;
if(num<=mid){
overkill_rgt(nd, s, e, num);
if(nd->lc)upd_swpr(nd->lc, s, (s+e)/2, num);
}
else{
push_rgt(nd, s, e, num);
if(nd->rc)upd_swpr(nd->rc, (s+e)/2+1, e, num);
}
}
void upd_ins(pii rn, int num){
rn.S=n-rn.S;
upd_ins(rt, 0, n, rn, num);
}
void upd_swpl(int num){upd_swpl(rt, 0, n, num);}
void upd_swpr(int num){upd_swpr(rt, 0, n, num);}
pii query(int num){
pii tmp=query(rt, 0, n, num);
tmp.S=n-tmp.S;
return tmp;
}
}seg;
int main(){
scanf("%d %d %d", &n, &m, &q);
for(int i=1; i<=m; i++){
int a, b;
scanf("%d %d", &a, &b);
seg.upd_ins(mp(a, b), ++re);
}
for(int i=1; i<=q; i++){
int a;
scanf("%d", &a);
if(a==1){
int b;
scanf("%d", &b);
pii ans=seg.query(b);
printf("??? %d %d\n", ans.F, ans.S);
}
if(a==2){
int b;
scanf("%d", &b);
seg.upd_swpl(n-b);
}
if(a==3){
int b;
scanf("%d", &b);
seg.upd_swpr(b);
}
if(a==4){
int b, c;
scanf("%d %d", &b, &c);
seg.upd_ins(mp(b, c), ++re);
}
}
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
sweeping.cpp:190:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b);
~~~~~^~~~~~~~~~
sweeping.cpp:196:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b);
~~~~~^~~~~~~~~~
sweeping.cpp:201:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b);
~~~~~^~~~~~~~~~
sweeping.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &b, &c);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8010 ms |
751112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3213 ms |
249048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3213 ms |
249048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
