oj.uz

Submission #617095

# Submission time Handle Problem Language Result Execution time Memory
617095 2022-08-01T08:40:28 Z 조영욱(#8505) Sweeping (JOI20_sweeping) C++17
0 / 100
 2054 ms 31184 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 (seg[node]<lazy[node]) {
            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]);
            }
        }
    }
    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 max(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]=max(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;
                }
            }
            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;
                }
            }
            seg2.upd(0,lo,n-l);
        }
    }
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
sweeping.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |             scanf("%d",&p);
      |             ~~~~~^~~~~~~~~
sweeping.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |             scanf("%d",&l);
      |             ~~~~~^~~~~~~~~
sweeping.cpp:95:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |             scanf("%d",&l);
      |             ~~~~~^~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 16788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1461 ms 27272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2054 ms 31184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 2054 ms 31184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 16788 KB Output isn't correct
2 Halted 0 ms 0 KB -