Submission #1148432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148432		arkanefury	Meteors (POI11_met)	C++17	74 / 100	6095 ms	18416 KiB

met

#include <bits/stdc++.h>  
#define pb push_back  
using namespace std;  
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)  
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)  
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);  
const int N = 3e5+150;  
int n,m,k,tt,ans,l, r, x, y, cnt; 
int b[N],a[N], sum, root[N], block = 600, d[N], e[N], f[N], ko[N], t[N*6], c[N];
vector<int>v[N];
vector <int> g[600];
int siz = 1;
void upd(int v, int l, int r, int val, int tl = 1, int tr = m){
    if(l > tr || tl > r)return;
    if(l <= tl && tr <= r){
        t[v] += val;
        return;
    }
    int tm = (tl + tr) >> 1;
    upd(v*2, l, r, val, tl, tm);
    upd(v*2+1, l, r, val, tm+1, tr);
}
void get(int v, int pos, int tl = 1, int tr = m){
        ans += t[v];
        ans = min(ans, (int)1e9);
    if(tl == tr){
        return;
    }
    int tm = (tl + tr) >> 1;
    if( pos <= tm )get(v*2, pos, tl, tm);
    else get(v*2+1, pos, tm+1, tr);
}
void clear(int v = 1, int tl = 1, int tr = m){
    t[v] = 0;
    if(tl==tr)return;
    int tm = (tl+tr) >> 1;
    clear(v*2, tl, tm), clear(v*2+1, tm+1, tr);
}
void solve(){
    nikita
    cin >> n >> m;
    FOR(i, 1, m, 1){
        cin >> a[i];
        v[a[i]].pb(i);
    }
    FOR(i, 1, n, 1)cin >> b[i];
    cin >> k;
    FOR(i, 1, k, 1){
        cin >> d[i] >> e[i] >> f[i];
        x = d[i], y = e[i], cnt = f[i];
        if(x <= y){
            upd(1, x, y, cnt);
            if(b[i/block] != b[(i+1)/block] || i == k){
                FOR(j, 1, n, 1){
                    if(c[j])continue;
                    ans = 0;
                    for(auto ok : v[j]){
                        get(1, ok);
                    }
                if(!c[j] && ans >= b[j])c[j] = 1,g[i/block].pb(j);
                }
            }
        }
        else{
            upd(1, x, m, cnt), upd(1, 1, y, cnt);
            if(b[i/block] != b[(i+1)/block] || i == k){
                FOR(j, 1, n, 1){
                    if(c[j])continue;
                    ans = 0;
                    for(auto ok : v[j]){
                        get(1, ok);
                    }
                if(!c[j] && ans >= b[j])c[j] = 1,g[i/block].pb(j);
                }
            }
        }
    }
    clear();
    FOR(i, 1, k, 1){
        x = d[i], y = e[i], cnt = f[i];
        if(x <= y){
            upd(1, x, y, cnt);
        }
        else{
            upd(1, x, m, cnt), upd(1, 1, y, cnt);
        }
        for(auto j : g[i/block]){
            if(ko[j])continue;
            ans = 0;
            for(auto ok : v[j])get(1, ok);
            if(ans >= b[j])ko[j] = i;
        }
    }
    FOR(i, 1, n, 1){
        if(!ko[i])cout << "NIE\n";
        else cout << ko[i] << '\n';
    }
}
signed main()  
{  
    nikita  
    tt = 1;  
    if(!tt)cin >> tt;  
    FOR(i, 1, tt, 1){  
    solve();  
    }  
}

• 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