답안 #865359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
865359	2023-10-24T07:40:55 Z	vjudge1	Meteors (POI11_met)	C++	74 / 100	188 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,mid
#define TR v+v+1,mid+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 DO{int sum;int l;int r;};

int n,m,a[N],p[N],q,sz,root[N];
DO t[10*N];
set <int> d[N];

int upd(int v,int l,int r,int val,int tl=1,int tr=m) {
    if (tl>r or tr<l)
        return v;
    int nv=++sz;
    if (tl!=tr and !t[v].l)
        t[v].l=++sz, t[v].r=++sz;
    t[nv]=t[v];
    if (tl>=l and tr<=r) {
        t[nv].sum+=val;
        t[nv].sum=min(t[nv].sum,(int)1e9);
        return nv;
    }
    t[nv].l=upd(t[v].l,l,r,val,tl,md), t[nv].r=upd(t[v].r,l,r,val,md+1,tr);
    return nv;
}

int upd1(int v,int l1,int r1, int l2,int r2,int val,int tl=1,int tr=m) {
    if ((tl>r1 or tr<l1) and (tl>r2 or tr<l2))
        return v;
    int nv=++sz;
    if (tl!=tr and !t[v].l)
        t[v].l=++sz, t[v].r=++sz;
    t[nv]=t[v];
    if (tl>=l1 and tr<=r1) {
        t[nv].sum+=val;
        t[nv].sum=min(t[nv].sum,(int)1e9);
        if (tl>r2 or tr<l2)
            return nv;
    }
    if (tl>=l2 and tr<=r2) {
        t[nv].sum+=val;
        t[nv].sum=min(t[nv].sum,(int)1e9);
        if (tl>r1 or tr<l1)
            return nv;
    }
    t[nv].l=upd1(t[v].l,l1,r1,l2,r2,val,tl,md), t[nv].r=upd1(t[v].r,l1,r1,l2,r2,val,md+1,tr);
    return nv;
}

int sum;

int get(int v,int pos,int tl=1,int tr=m) {
    sum+=t[v].sum;
    sum=min(sum,(int)1e9);
    if (tl==tr)
        return sum;
    if (pos<=md)
        return get(t[v].l,pos,tl,md);
    else
        return get(t[v].r,pos,md+1,tr);
}

int calc(int i,int v) {
    if (v==0)
        return 0;
    int suum=0;
    for (auto now : d[i])
        sum=0,suum+=get(root[v],now), suum=min(suum,(int)1e9);
    return suum;
}

int l,r;

int bs(int i) {
    int mid;
    l=-1,r=q+1;
    while (l+1<r) {
        mid=(l+r)/2;
        if (calc(i,mid)>=p[i])
            r=mid;
        else
            l=mid;
    }
    return r;
}

void solve() {
    cin >> n >> m;
    for (int i=1;i<=m;i++)
        cin >> a[i], d[a[i]].insert(i);
    for (int i=1;i<=n;i++)
        cin >> p[i];
    cin >> q;
    for (int i=1;i<=q;i++) {
        int v;
        cin >> l >> r >> v;
        if (l>r)
            root[i]=upd1(root[i-1],l,m,1,r,v);
        else
            root[i]=upd(root[i-1],l,r,v);
    }
    for (int i=1;i<=n;i++) {
        if (bs(i)==q+1)
            cout << "NIE\n";
        else
            cout << bs(i) << '\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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	16984 KB	Output is correct
2	Correct	4 ms	17240 KB	Output is correct
3	Correct	4 ms	16988 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	16988 KB	Output is correct
2	Correct	4 ms	16988 KB	Output is correct
3	Correct	5 ms	16988 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	127 ms	44324 KB	Output is correct
2	Correct	123 ms	46672 KB	Output is correct
3	Correct	188 ms	44252 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	126 ms	44116 KB	Output is correct
2	Correct	141 ms	44212 KB	Output is correct
3	Correct	150 ms	46416 KB	Output is correct
4	Correct	57 ms	21596 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	33872 KB	Output is correct
2	Correct	101 ms	42324 KB	Output is correct
3	Correct	26 ms	29524 KB	Output is correct
4	Correct	131 ms	44332 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	46372 KB	Output is correct
2	Correct	162 ms	46416 KB	Output is correct
3	Correct	112 ms	44116 KB	Output is correct
4	Correct	138 ms	46408 KB	Output is correct

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	105 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	114 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

답안 #865359

Compilation message