oj.uz

Submission #817023

# Submission time Handle Problem Language Result Execution time Memory
817023 2023-08-09T08:36:38 Z 반딧불(#10124) Ants and Sugar (JOI22_sugar) C++17
0 / 100
 408 ms 31976 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    ll rx[1<<22], ry[1<<22], vx[1<<22], vy[1<<21];

    inline ll rev(int i, ll x){
        return rx[i] - (ry[i] - x);
    }

    void update(int i, int l, int r, int x, ll a, ll s){
        if(l==r){
            rx[i] = a, ry[i] = s, vx[i] = max(a-s, 0LL), vy[i] = a;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, a, s);
        else update(i*2+1, m+1, r, x, a, s);
        ry[i] = max(0LL, ry[i*2+1] - max(0LL, rx[i*2+1] - ry[i*2]));
        rx[i] = ry[i] == 0 ? 0 : max(0LL, rx[i*2] - (ry[i*2] - (rx[i*2+1] - (ry[i*2+1] - ry[i]))));
        vy[i] = vy[i*2] + min(vy[i*2+1], vy[i*2+1] - (vx[i*2+1] - ry[i*2]));
        vx[i] = (vy[i] == vy[i*2]) ? vx[i*2] : (vy[i] == vy[i*2] + vy[i*2+1]) ? max(vx[i*2], rev(i*2, vx[i*2+1])) :
               max(rx[i*2], vx[i*2+1] - ry[i*2] + rx[i*2]) - (vy[i*2] + vy[i*2+1] - vy[i]);
    }

    ll query(){
        return vy[1] - vx[1];
    }
} tree;

int q; ll L; int LEN;
int qt[500002]; ll qx[500002], qv[500002];
ll ant[1500002], sugar[1500002];

void renumber(){
    vector<ll> vx;
    for(int i=1; i<=q; i++){
        vx.push_back((qx[i])/2);
        vx.push_back((qx[i]+1)/2);
        vx.push_back((qx[i]+2)/2);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    for(int i=1; i<=q; i++){
        qx[i] = lower_bound(vx.begin(), vx.end(), (qx[i]+1)/2) - vx.begin();
    }
    LEN = (int)vx.size() - 1;
}

int main(){
    scanf("%d %lld", &q, &L);
    for(int i=1; i<=q; i++){
        scanf("%d %lld %lld", &qt[i], &qx[i], &qv[i]);
    }
    renumber();
    for(int i=1; i<=q; i++){
        if(qt[i] == 1) ant[qx[i]] += qv[i];
        else sugar[qx[i]] += qv[i];
        tree.update(1, 0, LEN, qx[i], ant[qx[i]], sugar[qx[i]]);
        printf("%lld\n", tree.query());
    }
}

Compilation message

sugar.cpp: In function 'int main()':
sugar.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %lld", &q, &L);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sugar.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %lld %lld", &qt[i], &qx[i], &qv[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 408 ms 31976 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

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

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -