제출 #1149799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149799		arkanefury	새로운 문제 (POI11_met)	C++17	100 / 100	2882 ms	61696 KiB

met

#include <bits/stdc++.h>  
#define pb push_back  
using namespace std; 
#define F first
#define S second
#define ll long long
#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],q, L[N], R[N], lp[N], pl[N], ko[N], ans1[N];
vector<int>check[N], g[N];
ll t[2 * N];
 
void upd( int l, int r, int val )
{
    l += m, r += m + 1;
    
    while( l < r ) 
 {
        if( l & 1 ) t[l ++] += val;
        if( r & 1 ) t[-- r] += val;
        l >>= 1;
        r >>= 1;
    }
}
ll get( int pos )
{
    pos += m;
    ll res = 0;
    
    while( pos > 0 )
 {
        res += t[pos];
        pos >>= 1;
}
    return res;
}

void solve(){
    nikita
    cin >> n >> m;
    FOR(i, 1, m, 1){
        cin >> a[i];
        g[a[i]].pb(i);
    }
    FOR(i, 1, n, 1)cin >> b[i];
    cin >> q;
    FOR(i, 1, n, 1)L[i] = 1, R[i] = q;
    FOR(i, 1, q, 1){
        cin >> lp[i] >> pl[i] >> ko[i];
    }
    while(1){
        bool qwerty     = 0;
        FOR(j, 1, n, 1){
        if(R[j] >= L[j])check[(L[j] + R[j]) >> 1].pb(j), qwerty = 1;
       }
       if(!qwerty)break;
       FOR(j, 1, q, 1){
           if(lp[j] > pl[j]){
               upd(lp[j], m, ko[j]);
               upd(1, pl[j], ko[j]);
           }
           else upd(lp[j], pl[j], ko[j]);
           for(auto ok : check[j]){
               ll sum = 0;
               for(auto dety : g[ok]){
                   sum += get(dety);
                   if(sum >= b[ok])break;
               }
               if(sum >= b[ok])ans1[ok] = j, R[ok] = j - 1;
               else L[ok] = j + 1;
           }
           check[j].clear();
       }
       FOR(j, 1, q, 1){
           if(lp[j] > pl[j]){
               upd(lp[j], m, -ko[j]);
               upd(1, pl[j], -ko[j]);
           }
           else upd(lp[j], pl[j], -ko[j]);
       }
    }
    FOR(i, 1, n, 1){
        if(!ans1[i])cout << "NIE\n";
        else cout <<ans1[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: 13 / 13
• Subtask 8: 13 / 13