Submission #865734

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
865734	2023-10-24T14:57:51 Z	vjudge1	Meteors (POI11_met)	C++	100 / 100	3631 ms	65536 KB

// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
// #define int long long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,md
#define TR v+v+1,md+1,tr

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;

int binpow(int a,int n,int M) {
    if (n==0)
        return 1;
    if (n%2!=0)
        return (a * binpow(a,n-1,M))%M;
    int z=binpow(a,n/2,M);
    return (z*z)%M;
}

const ll INF = 1e18;
const int N =  3e5+7;
const int M = 1e9+7;
const ll HZ = 1e5;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;

struct segment{int l;int r;};

int n,m,q,a[N],p[N],t[4*N];
segment seg[N];
vector <int> MID[N];

void push(int v) {
    t[v+v]+=t[v], t[v+v+1]+=t[v];
    t[v+v]=min(t[v+v],(int)1e9);
    t[v+v+1]=min(t[v+v+1],(int)1e9);
    t[v]=0;
}

void upd(int l,int r,int val,int v=1,int tl=1,int tr=m) {
    if (tl>=l and tr<=r) {
        t[v]+=val;
        t[v]=min(t[v],(int)1e9);
        return;
    }
    if (tl>r or tr<l)
        return;
    push(v);
    upd(l,r,val,TL), upd(l,r,val,TR);
}

int get(int pos,int v=1,int tl=1,int tr=m) {
    if (tl==tr)
        return t[v];
    push(v);
    if (pos<=md)
        return get(pos,TL);
    else
        return get(pos,TR);
}

int l[N],r[N],v[N];
vector <int> pos[N];

void solve() {
    cin >> n >> m;
    for (int i=1;i<=m;i++)
        cin >> a[i], pos[a[i]].push_back(i);
    for (int i=1;i<=n;i++)
        cin >> p[i];
    cin >> q;
    for (int i=1;i<=q;i++)
        cin >> l[i] >> r[i] >> v[i];
    for (int i=1;i<=n;i++)
        seg[i].l=-1,seg[i].r=q+1;
    bool ok=true;
    while (ok) {
        for (int i=0;i<=q;i++)
            MID[i].clear();
        for (int i=0;i<=4*N-1;i++)
            t[i]=0;
        ok=false;
        for (int i=1;i<=n;i++) {
            // cout << seg[i].l << ' ' << seg[i].r << endl;
            if (seg[i].l+1<seg[i].r) {
                int mid = (seg[i].l + seg[i].r) / 2;
                MID[mid].push_back(i);
                ok=true;
            }
        }
        // cout << endl;
        for (int i=0;i<=q;i++) {
            if (i>0) {
                if (l[i] > r[i])
                    upd(l[i], m, v[i]), upd(1, r[i], v[i]);
                else
                    upd(l[i], r[i], v[i]);
            }
            for (auto now : MID[i]) {
                int sum=0;
                for (auto now1 : pos[now]) {
                    sum += get(now1);
                    sum=min(sum,(int)1e9);
                }
                if (sum>=p[now])
                    seg[now].r=i;
                else
                    seg[now].l=i;
            }
        }
    }
    for (int i=1;i<=n;i++) {
        if (seg[i].r==q+1)
            cout << "NIE\n";
        else
            cout << seg[i].r << '\n';
    }
}

signed main() {
    // freopen("lca.in", "r", stdin);
    // freopen("lca.out", "w", stdout);
    kanagattandirilmagandiktarinizdan
    int test = 1, count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test)
            // cout << '\n';
            count++;
    }
    return 0;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	27228 KB	Output is correct
2	Correct	8 ms	27340 KB	Output is correct
3	Correct	8 ms	27228 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	27228 KB	Output is correct
2	Correct	8 ms	27328 KB	Output is correct
3	Correct	9 ms	27228 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	321 ms	27988 KB	Output is correct
2	Correct	373 ms	29800 KB	Output is correct
3	Correct	349 ms	29524 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	345 ms	29008 KB	Output is correct
2	Correct	342 ms	29012 KB	Output is correct
3	Correct	375 ms	30028 KB	Output is correct
4	Correct	79 ms	28752 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	166 ms	28496 KB	Output is correct
2	Correct	264 ms	30256 KB	Output is correct
3	Correct	152 ms	27228 KB	Output is correct
4	Correct	344 ms	29836 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	347 ms	27624 KB	Output is correct
2	Correct	313 ms	28916 KB	Output is correct
3	Correct	330 ms	27728 KB	Output is correct
4	Correct	366 ms	30964 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3025 ms	39928 KB	Output is correct
2	Correct	1788 ms	29028 KB	Output is correct
3	Correct	820 ms	27564 KB	Output is correct
4	Correct	3631 ms	64172 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3016 ms	38592 KB	Output is correct
2	Correct	1227 ms	28636 KB	Output is correct
3	Correct	664 ms	27340 KB	Output is correct
4	Correct	3387 ms	65536 KB	Output is correct

Submission #865734

Compilation message