Submission #1148380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148380		arkanefury	Meteors (POI11_met)	C++17	74 / 100	109 ms	73004 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],block = 448, mod = 1e9+7, a[N], sum, root[N];
string str;
vector<int>v[N];
struct{
    int l, r, s;
}t[N*17];
int siz = 1;
int upd(int v, int l, int r, int val, int tl = 1, int tr = m){
    int nv = ++siz;
    t[nv] = t[v];
    if(l <= tl && tr <= r){
        t[nv].s += val;
        return nv;
    }
    if(l > tr || tl > r)return v;
    int tm = (tl + tr) >> 1;
    t[nv].l = upd(t[nv].l, l, r, val, tl, tm);
    t[nv].r = upd(t[nv].r, l, r, val, tm+1, tr);
    return nv;
}
void get(int v, int pos, int tl = 1, int tr = m){
        ans += t[v].s;
        ans = min(ans, (int)1e9);
    if(tl == tr){
        return;
    }
    int tm = (tl + tr) >> 1;
    if( pos <= tm )get(t[v].l, pos, tl, tm);
    else get(t[v].r, pos, 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 >> x >> y >> cnt;
        if(x <= y){
            root[i] = upd(root[i-1], x, y, cnt);
        }
        else{
            root[i] = upd(root[i-1], x, m, cnt);
            root[i] = upd(root[i], 1, y, cnt);
        }
    }
    FOR(i, 1, n, 1){
            l = 1, r = k;
            int lp = 0;
            while(l <= r){
                int md = (l + r) >> 1;
                ans = 0;
        for(auto j : v[i]){
                get(root[md], j);
            }
            if(ans < b[i])l = md + 1, lp = md;
            else r = md - 1;
        }
        if(l == k + 1)cout << "NIE\n";
        else cout << lp + 1 << '\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