oj.uz

Submission #816742

# Submission time Handle Problem Language Result Execution time Memory
816742 2023-08-09T06:27:16 Z 이동현(#10127) Ants and Sugar (JOI22_sugar) C++17
0 / 100
 1 ms 320 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Seg{
    int n;
    vector<vector<int>> tr;

    Seg(int m){
        n = m + 4;
        tr.resize(n * 4 + 4, vector<int>(4));
    }

    vector<int> merge(vector<int> x, vector<int> y){
        vector<int> rv(4);
        rv[0] = min({x[1] + y[0], x[1] + y[2], x[0] + y[2]});
        rv[1] = min({x[1] + y[1], x[1] + y[3], y[0] + y[3]});
        rv[2] = min({x[3] + y[0], x[3] + y[2], x[2] + y[2]});
        rv[3] = min({x[3] + y[1], x[3] + y[3], x[2] + y[3]});
        return rv;
    }

    void push(int x, int s, int e, int pos, int val){
        if(s == e){
            tr[x] = {0, (int)1e18, (int)1e18, tr[x][3] + val};
            return;
        }

        int m = s + e >> 1;
        if(pos <= m) push(x * 2, s, m, pos, val);
        else push(x * 2 + 1, m + 1, e, pos, val);

        tr[x] = merge(tr[x * 2], tr[x * 2 + 1]);
    }

    vector<int> get(int x, int s, int e, int fs, int fe){
        if(fe < s || fs > e) return {0, 0, 0, 0};
        if(fs <= s && fe >= e){
            return tr[x];
        }

        int m = s + e >> 1;
        return merge(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int q, L;
    cin >> q >> L;
    Seg tr(q + 4);
    for(int rep = 0; rep < q; ++rep){
        int t, x, a;
        cin >> t >> x >> a;
        tr.push(1, 0, q - 1, x, a);

        cout << *min_element(tr.tr[1].begin(), tr.tr[1].end()) << '\n';
    }
    
    return 0;
}

Compilation message

sugar.cpp: In member function 'void Seg::push(long long int, long long int, long long int, long long int, long long int)':
sugar.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int m = s + e >> 1;
      |                 ~~^~~
sugar.cpp: In member function 'std::vector<long long int> Seg::get(long long int, long long int, long long int, long long int, long long int)':
sugar.cpp:45:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int m = s + e >> 1;
      |                 ~~^~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 52.0

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