| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1047088 |
2024-08-07T08:51:01 Z |
정희우(#11025) |
청소 (JOI20_sweeping) |
C++17 |
|
18000 ms |
902320 KB |
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;
const int MAX_Q=1000010;
struct Obj
{
int x,d,i;
bool operator < (const Obj &o) const
{
if(x!=o.x)return x<o.x;
return d<o.d;
}
};
struct Segtree
{
struct Seg
{
int xi,yi;
Seg()
{
xi=yi=MAX_Q;
}
void upd(int d,int i)
{
if(d==0) xi=i;
else yi=i;
}
};
int sz;
vector<Obj> obj;
vector<Seg> seg;
void merge_(Seg &p,const Seg &l,const Seg &r)
{
p.xi=l.xi;
if(l.yi>r.xi)p.xi=min(p.xi,r.xi);
p.yi=r.yi;
if(r.xi>l.yi)p.yi=min(p.yi,l.yi);
}
void init_seg(int i,int s,int e)
{
if(s+1==e)
{
seg[i].upd(obj[s].d,obj[s].i);
return;
}
init_seg(i<<1,s,(s+e)>>1);
init_seg(i<<1|1,(s+e)>>1,e);
merge_(seg[i],seg[i<<1],seg[i<<1|1]);
}
Seg find_(int i,int s,int e,int l,int r)
{
if(s>=r || e<=l)return {};
if(l<=s && e<=r)return seg[i];
Seg v;
merge_(v,find_(i<<1,s,(s+e)>>1,l,r),find_(i<<1|1,(s+e)>>1,e,l,r));
return v;
}
int findx(int i,int s,int e,int l,int r,Seg j)
{
if(s>=r || e<=l)return -1;
if(l<=s && e<=r && seg[i].xi>=j.yi)return -1;
if(s+1==e)return s;
Seg j2;
merge_(j2,j,find_(i<<1,s,(s+e)>>1,l,r));
int v=findx(i<<1|1,(s+e)>>1,e,l,r,j2);
if(v!=-1)return v;
return findx(i<<1,s,(s+e)>>1,l,r,j);
}
int findy(int i,int s,int e,int l,int r,Seg j)
{
if(s>=r || e<=l)return -1;
if(l<=s && e<=r && seg[i].yi>=j.xi)return -1;
if(s+1==e)return s;
Seg j2;
merge_(j2,find_(i<<1|1,(s+e)>>1,e,l,r),j);
int v=findy(i<<1,s,(s+e)>>1,l,r,j2);
if(v!=-1)return v;
return findy(i<<1|1,(s+e)>>1,e,l,r,j);
}
int max_i(int i,int s,int e)
{
if(s+1==e)
return i;
return max_i(i<<1|1,(s+e)>>1,e);
}
void init_()
{
sz=obj.size();
sort(obj.begin(),obj.end());
seg.resize(max_i(1,0,sz)+1);
init_seg(1,0,sz);
Seg v;
}
pii calc(pii p)
{
int lx=p.first,rx=p.second;
int l=lower_bound(obj.begin(),obj.end(),(Obj){lx,0,0})-obj.begin();
int r=upper_bound(obj.begin(),obj.end(),(Obj){rx,1,0})-obj.begin();
int fx=findx(1,0,sz,l,r,(Seg){});
int fy=findy(1,0,sz,l,r,(Seg){});
if(fx!=-1)
lx=obj[fx].x;
if(fy!=-1)
rx=obj[fy].x;
return {lx,rx};
}
};
struct Ask
{
pii p;
int l,r;
};
int n,m,q;
vector<pii> pos;
vint pin;
vector<Obj> qry;
vector<Ask> ask;
Segtree sseg[MAX_Q<<2];
void init_(int i,int s,int e)
{
if(i>=MAX_Q<<2)while(1);
if(s+1==e)
{
sseg[i].obj.push_back(qry[s]);
sseg[i].init_();
return;
}
init_(i<<1,s,(s+e)>>1);
init_(i<<1|1,(s+e)>>1,e);
for(auto o : sseg[i<<1].obj)
sseg[i].obj.push_back(o);
for(auto o : sseg[i<<1|1].obj)
sseg[i].obj.push_back(o);
sseg[i].init_();
}
pii calc(int i,int s,int e,int l,int r,pii p)
{
if(s>=r || e<=l)return p;
if(l<=s && e<=r)return sseg[i].calc(p);
return calc(i<<1|1,(s+e)>>1,e,l,r,calc(i<<1,s,(s+e)>>1,l,r,p));
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m >> q;
for(int i=0;i<m;i++)
{
int x,y;
cin >> x >> y;
pos.push_back({x,n-y});
pin.push_back(0);
}
for(int i=0;i<q;i++)
{
int t,x,y;
cin >> t >> x;
if(t==1)
{
if(x-1>=pos.size())while(1);
ask.push_back({pos[x-1],pin[x-1],(int)qry.size()});
}
else if(t==2)
qry.push_back({n-x,0,(int)qry.size()});
else if(t==3)
qry.push_back({x,1,(int)qry.size()});
else
{
cin >> y;
pos.push_back({x,n-y});
pin.push_back(qry.size());
}
}
int qn=qry.size();
init_(1,0,qn);
for(auto a : ask)
{
pii p=calc(1,0,qn,a.l,a.r,a.p);
cout << p.first << ' ' << n-p.second << '\n';
}
return 0;
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:172:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | if(x-1>=pos.size())while(1);
| ~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
44 ms |
220496 KB |
Output is correct |
| 2 |
Correct |
46 ms |
220508 KB |
Output is correct |
| 3 |
Execution timed out |
18056 ms |
219740 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3160 ms |
552628 KB |
Output is correct |
| 2 |
Correct |
3291 ms |
550528 KB |
Output is correct |
| 3 |
Correct |
3315 ms |
552716 KB |
Output is correct |
| 4 |
Correct |
1159 ms |
550900 KB |
Output is correct |
| 5 |
Correct |
1235 ms |
551748 KB |
Output is correct |
| 6 |
Correct |
1805 ms |
549104 KB |
Output is correct |
| 7 |
Correct |
3519 ms |
551080 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3687 ms |
570620 KB |
Output is correct |
| 2 |
Correct |
3499 ms |
570512 KB |
Output is correct |
| 3 |
Correct |
1783 ms |
569844 KB |
Output is correct |
| 4 |
Correct |
2385 ms |
570372 KB |
Output is correct |
| 5 |
Correct |
3445 ms |
570280 KB |
Output is correct |
| 6 |
Correct |
3631 ms |
570484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3687 ms |
570620 KB |
Output is correct |
| 2 |
Correct |
3499 ms |
570512 KB |
Output is correct |
| 3 |
Correct |
1783 ms |
569844 KB |
Output is correct |
| 4 |
Correct |
2385 ms |
570372 KB |
Output is correct |
| 5 |
Correct |
3445 ms |
570280 KB |
Output is correct |
| 6 |
Correct |
3631 ms |
570484 KB |
Output is correct |
| 7 |
Correct |
3381 ms |
570432 KB |
Output is correct |
| 8 |
Correct |
3503 ms |
570448 KB |
Output is correct |
| 9 |
Correct |
3376 ms |
570548 KB |
Output is correct |
| 10 |
Correct |
1820 ms |
570016 KB |
Output is correct |
| 11 |
Correct |
2365 ms |
570416 KB |
Output is correct |
| 12 |
Correct |
3463 ms |
570372 KB |
Output is correct |
| 13 |
Correct |
3346 ms |
570544 KB |
Output is correct |
| 14 |
Correct |
989 ms |
902320 KB |
Output is correct |
| 15 |
Execution timed out |
18051 ms |
247664 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
44 ms |
220496 KB |
Output is correct |
| 2 |
Correct |
46 ms |
220508 KB |
Output is correct |
| 3 |
Execution timed out |
18056 ms |
219740 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
