oj.uz

Submission #679884

# Submission time Handle Problem Language Result Execution time Memory
679884 2023-01-09T15:11:45 Z browntoad Meteors (POI11_met) C++14
0 / 100
 503 ms 57208 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define SQ(x) (x)*(x)
#define f first
#define s second
#define pii pair<int, int>
#define endl '\n'
#define pb push_back

const ll mod = 1e9+7;
const ll maxn = 3e5+5;
const ll inf = (1ll<<60);
const ll iinf = 2e9;

ll pw(ll x, ll p){
    ll ret=1;
    while(p>0){
        if (p&1){
            ret*=x;
            ret%=mod;
        }
        x*=x;
        x%=mod;
        p>>=1;
    }
    return ret;
}
ll inv(ll x){
    return pw(x, mod-2);
}
int n, m, k;
vector<int> need(maxn), own(maxn), ans(maxn);
vector<int> ids[maxn];
int bit[20][maxn];
int cval[20][maxn];
void modify(int a, int val, int lay){
    while(a<maxn){
        bit[lay][a]+=val;
        a+=(a&-a);
    }
}
int query(int a, int lay){
    int ret=0;
    while(a>0){
        ret+=bit[lay][a];
        a-=(a&-a);
    }
    return ret;
}
struct mods{
    int l, r;
    int w;
};
vector<mods> quer;
void run(int l, int r, vector<int> &vals, int lay){
    if (SZ(vals)==0) return;
    if (l==r){
        REP(i, SZ(vals)){
            if (l==k) ans[vals[i]]=-1;
            else ans[vals[i]]=l+1;
        }
        return;
    }
    int mid = (l+r)>>1;
    FOR(i, l, mid+1){
        if (quer[i].l<=quer[i].r){
            modify(quer[i].l, quer[i].w, lay);
            modify(quer[i].r+1, -quer[i].w, lay);
        }
        else {
            modify(quer[i].l, quer[i].w, lay);
            modify(m+1, -quer[i].w, lay);
            modify(1, quer[i].w, lay);
            modify(quer[i].r+1, -quer[i].w, lay);
        }
    }
    vector<int> L, R;
    REP(i, SZ(vals)){
        REP(j, SZ(ids[vals[i]])){
            cval[lay][vals[i]]+=query(ids[vals[i]][j], lay);
        }
        if (cval[lay][vals[i]]>=need[vals[i]]){
            L.pb(vals[i]);
        }
        else{
            R.pb(vals[i]);
        }
    }
    run(l, mid, L, lay+1);
    run(mid+1, r, R, lay+1);
    FOR(i, mid+1, r+1){
        if (i>=k) break;
        if (quer[i].l<=quer[i].r){
            modify(quer[i].l, quer[i].w, lay);
            modify(quer[i].r+1, -quer[i].w, lay);
        }
        else {
            modify(quer[i].l, quer[i].w, lay);
            modify(m+1, -quer[i].w, lay);
            modify(1, quer[i].w, lay);
            modify(quer[i].r+1, -quer[i].w, lay);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    vector<int> tmp(n);
    REP(i, n){
        tmp[i]=i+1;
    }
    REP1(i, m){
        cin>>own[i];
        ids[own[i]].pb(i);
    }
    REP1(i, n){
        cin>>need[i];
    }
    cin>>k;
    REP(i, k){
        int x, y, z; cin>>x>>y>>z;
        quer.pb({x, y, z});
    }
    run(0, k, tmp, 0);
    REP1(i, n){
        if (ans[i]==-1) cout<<"NIE"<<endl;
        else cout<<ans[i]<<endl;
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 11348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11432 KB Output is correct
2 Correct 6 ms 11348 KB Output is correct
3 Incorrect 6 ms 11472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 16776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 17412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 16604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 16556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 503 ms 57208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 390 ms 54592 KB Output isn't correct
2 Halted 0 ms 0 KB -