Submission #680290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680290	2023-01-10T13:42:28 Z	browntoad	Meteors (POI11_met)	C++14	100 / 100	1511 ms	39488 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), ans(maxn);
vector<int> ids[maxn];
long long bit[maxn], incbit[maxn];
void modify(int a, int val){
    while(a<=m){
        bit[a]+=val;
        a+=(a&-a);
    }
}
void modify2(int a, int val){
    while(a<=m){
        incbit[a]+=val;
        a+=(a&-a);
    }
}
long long ret=0;
long long query(int a){
    ret=0;
    while(a>0){
        ret+=bit[a];
        a-=(a&-a);
    }
    return ret;
}
long long query2(int a){
    ret=0;
    while(a>0){
        ret+=incbit[a];
        a-=(a&-a);
    }
    return ret;
}
struct mods{
    int l, r;
    int w;
};
vector<mods> quer;
long long tmpv=0;
void run(int L, int R, vector<int> &vals, int lay){
    if (L>R) return;
    if (lay==20){
        REP(i, SZ(vals)){
            if (L==k) ans[vals[i]]=-1;
            else ans[vals[i]]=L+1;
        }
        if (L!=k){
            if (quer[L].l<=quer[L].r){
                modify2(quer[L].l, quer[L].w);
                modify2(quer[L].r+1, -quer[L].w);
            }
            else {
                modify2(quer[L].l, quer[L].w);
                modify2(m+1, -quer[L].w);
                modify2(1, quer[L].w);
                modify2(quer[L].r+1, -quer[L].w);
            }
        }
        return;
    }
    if (L==k){
        run(L, R, vals, lay+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);
            modify(quer[i].r+1, -quer[i].w);
        }
        else {
            modify(quer[i].l, quer[i].w);
            modify(m+1, -quer[i].w);
            modify(1, quer[i].w);
            modify(quer[i].r+1, -quer[i].w);
        }
    }
    vector<int> aL, aR;
    REP(i, SZ(vals)){
        tmpv=0;
        REP(j, SZ(ids[vals[i]])){
            tmpv+=query(ids[vals[i]][j])+query2(ids[vals[i]][j]);
            if (tmpv>=(ll)(need[vals[i]])) break;
        }
        if (tmpv>=(ll)(need[vals[i]])){
            aL.pb(vals[i]);
        }
        else{
            aR.pb(vals[i]);
        }
    }
    // undo
    FOR(i, L, mid+1){
        if (quer[i].l<=quer[i].r){
            modify(quer[i].l, -quer[i].w);
            modify(quer[i].r+1, quer[i].w);
        }
        else {
            modify(quer[i].l, -quer[i].w);
            modify(m+1, quer[i].w);
            modify(1, -quer[i].w);
            modify(quer[i].r+1, quer[i].w);
        }
    }
    run(L, mid, aL, lay+1);
    run(mid+1, R, aR, lay+1);


}
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;
    }
    int a;
    REP1(i, m){
        cin>>a;
        ids[a].pb(i);
    }
    REP1(i, n){
        cin>>need[i];
    }
    cin>>k;
    int x, y, z;
    REP(i, k){
        cin>>x>>y>>z;
        quer.pb({x, y, z});
    }
    fill(ALL(ans), -1);
    run(0, k, tmp, 0);
    REP1(i, n){
        if (ans[i]==-1) cout<<"NIE"<<endl;
        else cout<<ans[i]<<endl;
    }
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	7 ms	9812 KB	Output is correct
3	Correct	7 ms	9760 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	9772 KB	Output is correct
2	Correct	7 ms	9812 KB	Output is correct
3	Correct	7 ms	9744 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	12708 KB	Output is correct
2	Correct	128 ms	14708 KB	Output is correct
3	Correct	109 ms	12992 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	110 ms	12780 KB	Output is correct
2	Correct	114 ms	12804 KB	Output is correct
3	Correct	130 ms	14176 KB	Output is correct
4	Correct	40 ms	12100 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	12404 KB	Output is correct
2	Correct	107 ms	14300 KB	Output is correct
3	Correct	50 ms	11084 KB	Output is correct
4	Correct	110 ms	13200 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	12532 KB	Output is correct
2	Correct	115 ms	12940 KB	Output is correct
3	Correct	85 ms	12484 KB	Output is correct
4	Correct	125 ms	13832 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1077 ms	35036 KB	Output is correct
2	Correct	637 ms	27300 KB	Output is correct
3	Correct	222 ms	15168 KB	Output is correct
4	Correct	1265 ms	36380 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1012 ms	33648 KB	Output is correct
2	Correct	685 ms	25848 KB	Output is correct
3	Correct	195 ms	15608 KB	Output is correct
4	Correct	1511 ms	39488 KB	Output is correct

Submission #680290

Compilation message