oj.uz

답안 #816767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
816767 2023-08-09T06:32:58 Z 이동현(#10127) Ants and Sugar (JOI22_sugar) C++17
16 / 100
 1679 ms 149000 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, {0, (int)1e18, (int)1e18, 0});
    }

    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], x[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){
        // cout << x << ' ' << s << ' ' << e << ' ' << pos << ' ' << val << endl;
        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]);
        // cout << x << ' ' << s << ' ' << e << ' ' << pos << ' ' << val << endl;
        // cout << tr[x][0] << ' ' << tr[x][1] << ' ' << tr[x][2] << ' ' << tr[x][3] << endl;
    }

    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:33:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         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:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int m = s + e >> 1;
      |                 ~~^~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1162 ms 107752 KB Output is correct
5 Correct 341 ms 71472 KB Output is correct
6 Correct 1389 ms 125144 KB Output is correct
7 Correct 342 ms 72140 KB Output is correct
8 Correct 1597 ms 148436 KB Output is correct
9 Correct 722 ms 148924 KB Output is correct
10 Correct 1679 ms 148524 KB Output is correct
11 Correct 683 ms 149000 KB Output is correct
12 Correct 315 ms 64964 KB Output is correct
13 Correct 472 ms 89400 KB Output is correct
14 Correct 694 ms 145592 KB Output is correct
15 Correct 707 ms 145560 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -