oj.uz

Submission #850096

# Submission time Handle Problem Language Result Execution time Memory
850096 2023-09-15T17:56:47 Z nnin Meteors (POI11_met) C++14
100 / 100
 1488 ms 65536 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;

struct P {
    int l, r;
    ll a;
};

struct C{
    int l, r;
};

int n, m, q;
ll p[300003];
P predict[300003];
vector<int> own[300003];
C cur[300003];

ll fenwick[600003];
void update(int idx, ll val) {
    while(idx<=m) {
        fenwick[idx] += val;
        idx += (idx & -idx);
    }
}
ll query(int idx) {
    ll ret = 0;
    while(idx>0) {
        ret += fenwick[idx];
        idx -= (idx & -idx);
    }
    return ret;
}

vector<int> mid[300003];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int o;
        cin>>o;
        own[o].push_back(i);
    }
    for(int i=1;i<=n;i++) {
        cin>>p[i];
    }
    cin>>q;
    for(int i=1;i<=q;i++) {
        cin>>predict[i].l>>predict[i].r>>predict[i].a;
    }
    for(int i=1;i<=n;i++) {
        cur[i] = {1, q+1};
        mid[(2+q)/2].push_back(i);
    }
    int fin = 0;
    while(fin<n) {
        for(int i=0;i<=m;i++) fenwick[i] = 0;
        for(int i=1;i<=q;i++) {
            update(predict[i].l, predict[i].a);
            update(predict[i].r+1, -predict[i].a);
            if(predict[i].l>predict[i].r)
                update(1, predict[i].a);
            for(int state:mid[i]) {
                ll ct = 0;
                for(int station:own[state]) {
                    ct += query(station);
                    if(ct>=p[state]) break;
                }
                if(ct>=p[state]) {
                    cur[state].r = i;
                } else {
                    cur[state].l = i+1;
                }
                if(cur[state].l==cur[state].r) {
                    fin++;
                } else {
                    int md = (cur[state].l+cur[state].r)/2;
                    mid[md].push_back(state);
                }
            }
            mid[i].clear();
        }
    }
    for(int i=1;i<=n;i++) {
        if(cur[i].l==q+1) cout<<"NIE\n";
        else cout<<cur[i].l<<'\n';
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 23896 KB Output is correct
2 Correct 77 ms 25424 KB Output is correct
3 Correct 71 ms 25388 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 24916 KB Output is correct
2 Correct 74 ms 24888 KB Output is correct
3 Correct 77 ms 25624 KB Output is correct
4 Correct 22 ms 24664 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24408 KB Output is correct
2 Correct 65 ms 26448 KB Output is correct
3 Correct 32 ms 23128 KB Output is correct
4 Correct 70 ms 25680 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 23384 KB Output is correct
2 Correct 70 ms 24772 KB Output is correct
3 Correct 48 ms 23640 KB Output is correct
4 Correct 84 ms 26964 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 39732 KB Output is correct
2 Correct 530 ms 28764 KB Output is correct
3 Correct 158 ms 27732 KB Output is correct
4 Correct 1133 ms 65536 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 38472 KB Output is correct
2 Correct 602 ms 28624 KB Output is correct
3 Correct 144 ms 28700 KB Output is correct
4 Correct 1488 ms 65536 KB Output is correct