| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 617126 |
2022-08-01T08:51:11 Z |
조영욱(#8505) |
Sweeping (JOI20_sweeping) |
C++17 |
|
1714 ms |
28476 KB |
#include <bits/stdc++.h>
using namespace std;
const int sz=524288;
const int INF=1e9+7;
struct Seg {
int seg[sz*2];
int lazy[sz*2];
void init() {
for(int i=1;i<sz*2;i++) {
seg[i]=INF;
lazy[i]=INF;
}
}
void prop(int node) {
if (lazy[node]!=INF) {
seg[node]=max(seg[node],lazy[node]);
if (node<sz) {
lazy[node*2]=max(lazy[node*2],lazy[node]);
lazy[node*2+1]=max(lazy[node*2+1],lazy[node]);
}
lazy[node]=INF;
}
}
int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
prop(node);
if (r<nodel||l>noder) {
return INF;
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return min(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,r));
}
void upd(int l,int r,int val,int node=1,int nodel=0,int noder=sz-1) {
prop(node);
if (r<nodel||l>noder) {
return;
}
if (l<=nodel&&noder<=r) {
lazy[node]=max(lazy[node],val);
prop(node);
return;
}
int mid=(nodel+noder)/2;
upd(l,r,val,node*2,nodel,mid);
upd(l,r,val,node*2+1,mid+1,noder);
seg[node]=min(seg[node*2],seg[node*2+1]);
}
};
int n,m,q;
Seg seg1; //x��ǥ
Seg seg2; //y��ǥ
int main(void) {
scanf("%d %d %d",&n,&m,&q);
seg1.init();
seg2.init();
for(int i=0;i<m;i++) {
int x,y;
scanf("%d %d",&x,&y);
seg1.upd(i,i,x);
seg2.upd(i,i,y);
}
for(int i=0;i<q;i++) {
int type;
scanf("%d",&type);
//printf(".%d %d\n",seg1.sum(2,2),seg2.sum(2,2));
if (type==1) {
int p;
scanf("%d",&p);
p--;
printf("%d %d\n",seg1.sum(p,p),seg2.sum(p,p));
}
if (type==2) {
int l;
scanf("%d",&l);
int lo=-1; //y(lo)>l
int hi=m; //y(hi)<=l
while (lo+1<hi) {
int mid=(lo+hi)/2;
if (seg2.sum(mid,mid)<=l) {
hi=mid;
}
else {
lo=mid;
}
}
if (hi<m)
seg1.upd(hi,m-1,n-l);
}
if (type==3) {
int l;
scanf("%d",&l);
int lo=-1; //x(lo)<=l
int hi=m; //x(hi)>l
while (lo+1<hi) {
int mid=(lo+hi)/2;
if (seg1.sum(mid,mid)<=l) {
lo=mid;
}
else {
hi=mid;
}
}
if (lo>=0)
seg2.upd(0,lo,n-l);
}
}
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d %d",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d %d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d",&type);
| ~~~~~^~~~~~~~~~~~
sweeping.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
sweeping.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d",&l);
| ~~~~~^~~~~~~~~
sweeping.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d",&l);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1394 ms |
26188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1714 ms |
28476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1714 ms |
28476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
