제출 #1183319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183319		nguyenkhangninh99	새로운 문제 (POI11_met)	C++20	74 / 100	279 ms	38984 KiB

met

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 5e5 + 5;

int a[maxn], res[maxn], bit[maxn], ev[maxn][3];

vector<int> water, value[maxn];

void up(int x, int v){
    for (; x < maxn; x += x & -x) bit[x] += v;
}
int get(int x){
    int s = 0;
    for (; x > 0; x -= x & -x) s += bit[x];
    return s;
}
void add(int i, int v){
    if(ev[i][0] <= ev[i][1]){
        up(ev[i][0], (ev[i][2] * v));
        up(ev[i][1] + 1, -(ev[i][2] * v));
    }   
    else{
        up(1, (ev[i][2] * v));
        up(ev[i][1] + 1, -(ev[i][2] * v));
        up(ev[i][0], (ev[i][2] * v));
    }
}

int f(int x){
    int ans = 0;
    for(int id: value[x]){
        ans += get(id);
    }
    return ans;
}

void calc(int l, int r, vector<int>& cur){
    if(l > r || cur.empty()) return;
    int mid = (l + r) / 2;

    for(int i = l; i <= mid; i++) add(i, 1);
    vector<int> le, ri;
    for(int x: cur){
        int sum = f(x);
        if (sum >= a[x]){
            le.push_back(x);
            res[x] = mid;
        }else{
            ri.push_back(x);
            a[x] -= sum;
        }
    }
    for (int i = l; i <= mid; i++) add(i, -1);

    calc(l, mid - 1, le);
    calc(mid + 1, r, ri);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x; cin >> x;
        value[x].push_back(i);
    }

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        res[i] = -1;
        water.push_back(i);
    }

    int q; cin >> q;
    
    for(int i = 1; i <= q; i++) cin >> ev[i][0] >> ev[i][1] >> ev[i][2];
    
    calc(1, q, water);
    for(int i = 1; i <= n; i++){
        if(res[i] == -1) cout << "NIE\n";
        else cout << res[i] << '\n';
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13