oj.uz

Submission #475296

# Submission time Handle Problem Language Result Execution time Memory
475296 2021-09-21T19:10:14 Z nafis_shifat Food Court (JOI21_foodcourt) C++14
0 / 100
 287 ms 24580 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
using namespace std;
const int mxn=3e5+5;
const int inf=1e9;

int n,m,q;


struct segtree {
    
    ll removed[4 * mxn];
    
    pii tree[4 * mxn];

    void init(int n) {
        for(int i = 0; i < 4 * mxn; i++) tree[i] = {0,0};
    }

    pii merge(pii a, pii b) {
        return { b.f + max(0ll, a.f - b.s), a.s + max(0ll,b.s - a.f) };
    }


    void propogate(int node) {
        int left = node << 1;
        int right = left | 1;

        tree[left] = merge(tree[node], tree[left]);
        tree[right] = merge(tree[node], tree[right]);

        tree[node] = {0,0};
    }

    void update(int node,int b,int e,int l,int r, pii v) {
        if(e < l || b > r) return;
        if(b >= l && e <= r) {
            tree[node] = merge(v, tree[node]);
            // cout<<"After update"<<b<<" "<<e<<" "<<v.f<<" - "<<v.s<<" "<<tree[node].f<<" "<<tree[node].s<<endl;
            return;
        }
        if(tree[node].f != 0 || tree[node].s != 0) propogate(node);

        int mid = b + e >>1;
        int left = node << 1;
        int right = left | 1;

        update(left, b, mid, l, r, v);
        update(right, mid + 1, e, l, r, v);
    }

    ll query(int node,int b,int e,int p) {
        if(b == e) return tree[node].s;

        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;

        if(tree[node].f != 0 || tree[node].s != 0) propogate(node);

        if(p <= mid) return query(left,b,mid,p);
        return query(right, mid + 1,e,p);
    }
} st;

int main() {
    cin >> n >> m >> q;
    st.init(n);


    for(int i = 1; i <= q; i++) {
        int tp;
        scanf("%d",&tp);

        if(tp == 1) {
            int l,r,c;
            ll k;
            scanf("%d%d%d %lld",&l,&r,&c,&k);

            st.update(1,1,n,l,r,{0,k});
        } else if(tp == 2) {
            int l,r;
            ll k;
            scanf("%d%d %lld",&l,&r,&k);
            st.update(1,1,n,l,r,{k,0});
        } else {
            ll a,b;
            scanf("%lld %lld",&a,&b);

            if(st.query(1,1,n,a) >= b) printf("1\n");
            else printf("-1\n");
        }

    }


}

Compilation message

foodcourt.cpp: In member function 'void segtree::update(int, int, int, int, int, std::pair<long long int, long long int>)':
foodcourt.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = b + e >>1;
      |                   ~~^~~
foodcourt.cpp: In member function 'long long int segtree::query(int, int, int, int)':
foodcourt.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = b + e >> 1;
      |                   ~~^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d",&tp);
      |         ~~~~~^~~~~~~~~~
foodcourt.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |             scanf("%d%d%d %lld",&l,&r,&c,&k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |             scanf("%d%d %lld",&l,&r,&k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |             scanf("%lld %lld",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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