oj.uz

Submission #617151

# Submission time Handle Problem Language Result Execution time Memory
617151 2022-08-01T09:03:48 Z 조영욱(#8505) Sweeping (JOI20_sweeping) C++17
11 / 100
 3862 ms 43552 KB 
#include <bits/stdc++.h>
using namespace std;

const int sz=524288;
const int INF=1e9+7;
bool flag=false;

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 max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
    }
    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);
        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:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         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);
      |             ~~~~~^~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3862 ms 43552 KB Output is correct
2 Correct 3577 ms 29872 KB Output is correct
3 Correct 2581 ms 30584 KB Output is correct
4 Correct 2839 ms 30092 KB Output is correct
5 Correct 3587 ms 30124 KB Output is correct
6 Correct 3348 ms 29912 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3862 ms 43552 KB Output is correct
2 Correct 3577 ms 29872 KB Output is correct
3 Correct 2581 ms 30584 KB Output is correct
4 Correct 2839 ms 30092 KB Output is correct
5 Correct 3587 ms 30124 KB Output is correct
6 Correct 3348 ms 29912 KB Output is correct
7 Incorrect 3130 ms 30104 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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