Submission #1003497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003497		79brue	Food Court (JOI21_foodcourt)	C++17	100 / 100	334 ms	61008 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct segTree1{
    ll ta[1<<19], tb[1<<19];

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            if(v >= 0) ta[i] = v, tb[i] = 0;
            else ta[i] = 0, tb[i] = -v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        ta[i] = ta[i*2+1] + max(0LL, ta[i*2] - tb[i*2+1]);
        tb[i] = ta[i] + tb[i*2] + tb[i*2+1] - ta[i*2] - ta[i*2+1];
    }

    ll query(int i, int l, int r, int x, ll v=0){
        if(l==r) return ta[i] + max(0LL, v - tb[i]);
        int m = (l+r)>>1;
        if(x<=m) return query(i*2, l, m, x, v);
        else return query(i*2+1, m+1, r, x, ta[i*2] + max(0LL, v - tb[i*2]));
    }
} tree1;

struct segTree2{
    int n;
    ll tree[250002];

    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) tree[i] = 0;
    }

    void add(int x, ll v){
        while(x<=n){
            tree[x] += v;
            x += x&-x;
        }
    }

    ll sum(int x){
        ll ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
} tree2;

struct segTree3{
    ll sum[1<<19];

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            sum[i] = v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        sum[i] = sum[i*2] + sum[i*2+1];
    }

    int query(int i, int l, int r, ll v){
        if(l==r) return l;
        int m = (l+r)>>1;
        if(sum[i*2] >= v) return query(i*2, l, m, v);
        else return query(i*2+1, m+1, r, v - sum[i*2]);
    }
} tree3;

int n, m, q;
int qt[250002], ql[250002], qr[250002], qx[250002];
ll qk[250002];
ll qsz[250002], qall[250002], ord[250002];
vector<int> queries[250002];
vector<int> in[250002], out[250002];
int ans[250002];

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=q; i++){
        scanf("%d", &qt[i]);
        if(qt[i] == 1){
            scanf("%d %d %d %lld", &ql[i], &qr[i], &qx[i], &qk[i]);
            in[ql[i]].push_back(i);
            out[qr[i]].push_back(i);
        }
        else if(qt[i] == 2){
            scanf("%d %d %lld", &ql[i], &qr[i], &qk[i]);
            in[ql[i]].push_back(i);
            out[qr[i]].push_back(i);
        }
        else if(qt[i] == 3){
            scanf("%d %lld", &qx[i], &qk[i]);
            queries[qx[i]].push_back(i);
        }
    }

    /// 위치를 찾기
    for(int i=1; i<=n; i++){
        for(int p: in[i]) tree1.update(1, 1, q, p, qt[p] == 1 ? qk[p] : -qk[p]);
        for(int p: queries[i]) qsz[p] = tree1.query(1, 1, q, p);
        for(int p: out[i]) tree1.update(1, 1, q, p, 0);
    }

    /// 크기를 찾기
    tree2.init(n);
    for(int i=1; i<=q; i++){
        if(qt[i] == 1) tree2.add(ql[i], qk[i]), tree2.add(qr[i]+1, -qk[i]);
        else if(qt[i] == 3) qall[i] = tree2.sum(qx[i]);
    }

    for(int i=1; i<=q; i++){
        if(qt[i] != 3) continue;
        if(qk[i] <= qsz[i]) ord[i] = qall[i] - qsz[i] + qk[i];
    }

    /// 답을 찾기
    for(int i=1; i<=n; i++){
        for(int p: in[i]) if(qt[p] == 1) tree3.update(1, 1, q, p, qk[p]);
        for(int p: queries[i]){
            if(ord[p] == 0) continue;
            ans[p] = qx[tree3.query(1, 1, q, ord[p])];
        }
        for(int p: out[i]) if(qt[p] == 1) tree3.update(1, 1, q, p, 0);
    }

    for(int i=1; i<=q; i++) if(qt[i] == 3) printf("%d\n", ans[i]);
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%d", &qt[i]);
      |         ~~~~~^~~~~~~~~~~~~~
foodcourt.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |             scanf("%d %d %d %lld", &ql[i], &qr[i], &qx[i], &qk[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |             scanf("%d %d %lld", &ql[i], &qr[i], &qk[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |             scanf("%d %lld", &qx[i], &qk[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11