Submission #1148370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148370		arkanefury	Meteors (POI11_met)	C++17	24 / 100	1283 ms	131072 KiB

met

#include <bits/stdc++.h>  
#define pb push_back  
using namespace std;  
#define F first  
#define sz size()  
#define S second  
#define in insert
#define all(v) v.begin(), v.end()  
#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];
vector<int>v[N];
map<int, int>s, le, ri;
int siz = 1;
int upd(int v, int l, int r, int val, int tl = 1, int tr = m){
    int nv = ++siz;
    s[nv] = s[v], le[nv] = le[v], ri[nv] = ri[v];
    if(l <= tl && tr <= r){
        s[nv] += val;
        return nv;
    }
    if(l > tr || tl > r)return v;
    int tm = (tl + tr) >> 1;
    le[nv] = upd(le[nv], l, r, val, tl, tm);
    ri[nv] = upd(ri[nv], l, r, val, tm+1, tr);
    return nv;
}
void get(int v, int pos, int tl = 1, int tr = m){
        ans += s[v];
        ans = min(ans, (int)1e9);
    if(tl == tr){
        return;
    }
    int tm = (tl + tr) >> 1;
    if( pos <= tm )get(le[v], pos, tl, tm);
    else get(ri[v], 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: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13