oj.uz

답안 #955712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955712 2024-03-31T11:01:52 Z Vladth11 푸드 코트 (JOI21_foodcourt) C++14
0 / 100
 243 ms 41624 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 250002;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

vector <int> events[NMAX];
vector <int> queries[NMAX];

int t[NMAX];
pii q[NMAX];
int qq;

struct Node{
    int total, maxSuff;
}aint[NMAX * 4];

Node combine(Node a, Node b){
    Node sol = {a.total + b.total, max({b.maxSuff, a.maxSuff + b.total})};
    /// Am nevoie de cel mai mare sufix care se TERMINA IN MINE
    return sol;
}

void update(int node, int st, int dr, int a, int b){
    if(st == dr){
        aint[node] = {b, max(0, b)};

        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b);
    else update(node * 2 + 1, mid + 1, dr, a, b);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}

Node maxSuff(int node, int st, int dr, int a, int b){
    if(a <= st && dr <= b){
        return aint[node];
    }
    int mid = (st + dr) / 2;
    Node sol = {0, 0};
    if(a <= mid) sol = combine(sol, maxSuff(node * 2, st, mid, a, b));
    if(b > mid) sol = combine(sol, maxSuff(node * 2 + 1, mid + 1, dr, a, b));
    return sol;
}

pii aib[NMAX];

void baga(pii x, int val){
    aib[x.first].second = x.second;
    for(; x.first <= qq; x.first += x.first&(-x.first))
        aib[x.first].first += val;
}

int query(int x){
    int sol = 0;
    for(; x; x -= x&(-x))
        sol += aib[x].first;
    return sol;
}

int Search(int x){
    int r = 0, pas = (1 << nrbits), s = 0;
    while(pas){
        if(r + pas <= qq && (s + aib[r + pas].first) < x)
            r += pas;
        pas /= 2;
    }
    r++;
    return aib[r].second;
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, i;
    for(i = 0; i < NMAX * 4; i++) aint[i] = {0, 0};
    cin >> n >> m >> qq;
    for(i = 1; i <= qq; i++){
        cin >> t[i];
        if(t[i] == 3){
            cin >> q[i].first >> q[i].second;
            queries[q[i].first].push_back(i);
        }else if(t[i] == 2){
            int l, r;
            cin >> l >> r >> q[i].first;
            events[l].push_back(i);
            events[r + 1].push_back(-i);
        }else{
            int l, r;
            cin >> l >> r >> q[i].second >> q[i].first;
            events[l].push_back(i);
            events[r + 1].push_back(-i);
        }
    }
    for(i = 1; i <= n; i++){
        for(auto x : events[i]){
            if(x < 0){
                baga({-x, q[-x].second}, -q[-x].first);
                update(1, 1, qq, -x, 0);
            }else{
                if(t[x] == 1){
                    baga({x, q[x].second}, q[x].first);
                    update(1, 1, qq, x, q[x].first);
                }else{
                    update(1, 1, qq, x, -q[x].first);
                }
            }
        }
        for(auto x : queries[i]){
            int untilNow = query(x);
            int currentSize = maxSuff(1, 1, qq, 1, x).maxSuff;
            int b = q[x].second;
            if(b <= currentSize)
                cout << Search(untilNow - currentSize + b) << "\n";
            else
                cout << "0\n";
        }
    }
    return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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