oj.uz

Submission #681006

# Submission time Handle Problem Language Result Execution time Memory
681006 2023-01-12T08:38:18 Z uylulu Meteors (POI11_met) C++17
74 / 100
 1494 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

#define double long double
#define int long long
#define endl "\n"

const int N = 3e5 + 5,inf = 1e15;

int bit[N + 1];

vector<int> pos[N + 1];

struct some{
    int l,r,c;
};

some query[N + 1];
int le[N + 1],ri[N + 1],res[N + 1],d[N + 1];

vector<int> ask[N + 1];

int n,x;

inline void add(int pos,int val) {
    for(int i = pos;i <= x;i += i&(-i)) {
        bit[i] += val;
    }
}

inline int help(int pos) {
    int sum = 0;
    while(pos > 0) {
        sum += bit[pos];
        pos -= pos&(-pos);
    }
    return sum;
}

inline void init() {
    for(int i = 1;i <= x;i++) {
        bit[i] = 0;
    }
}

inline void range(int l,int r,int w) {
    if(l > r) {
        add(l,w);

        add(1,w);
        add(r + 1,-w);
    } else {
        add(l,w);
        add(r + 1,-w);
    }
}

bool vis[N + 1];

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);

    cin>>n>>x;

    for(int i = 1;i <= x;i++) {
        int val;
        cin>>val;

        pos[val].push_back(i);
    }
    for(int i = 1;i <= n;i++) {
        cin>>d[i];
    }
    int q;
    cin>>q;

    for(int i = 1;i <= q;i++) {
        cin>>query[i].l>>query[i].r>>query[i].c;

        range(query[i].l,query[i].r,query[i].c);
    }

    for(int i = 1;i <= n;i++) {
        le[i] = 1;
        ri[i] = q;
    }

    for(int i = 1;i <= n;i++) {
        for(auto u : pos[i]) {
            res[i] = min(inf,res[i] + help(u));
        }
        if(res[i] < d[i]) {
            vis[i] = true;
        }
    }


    for(int t = 0;t < 40;t++) {
        for(int i = 1;i <= q;i++) {
            ask[i].clear();
        }
        for(int i = 1;i <= n;i++) {
            if(le[i] == ri[i]) continue;

            int mid = (le[i] + ri[i])/2;

            ask[mid].push_back(i);

            res[i] = 0;
        }
        init();

        for(int i = 1;i <= q;i++) {


            range(query[i].l,query[i].r,query[i].c);

            for(auto u : ask[i]) {
                for(auto v : pos[u]) {
                    res[u] = min(inf,res[u] + help(v));
                }
            }
        }

        for(int i = 1;i <= n;i++) {
            if(le[i] == ri[i]) continue;

            int mid = (ri[i] + le[i])/2;

            if(res[i] >= d[i]) {
                ri[i] = mid;
            } else {
                le[i] = mid + 1;
            }
        }
    }

    for(int i = 1;i <= n;i++) {
        if(vis[i]) {
            cout<<"NIE"<<endl;
        } else {
            cout<<ri[i]<<endl;
        }
    }


    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14544 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 10 ms 14472 KB Output is correct
3 Correct 9 ms 14636 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 17528 KB Output is correct
2 Correct 171 ms 20852 KB Output is correct
3 Correct 147 ms 19780 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 19000 KB Output is correct
2 Correct 149 ms 19024 KB Output is correct
3 Correct 171 ms 21248 KB Output is correct
4 Correct 39 ms 18044 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17984 KB Output is correct
2 Correct 146 ms 21352 KB Output is correct
3 Correct 85 ms 15716 KB Output is correct
4 Correct 159 ms 20392 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 16528 KB Output is correct
2 Correct 171 ms 18892 KB Output is correct
3 Correct 112 ms 17116 KB Output is correct
4 Correct 169 ms 22616 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1494 ms 48600 KB Output is correct
2 Correct 1480 ms 26232 KB Output is correct
3 Correct 390 ms 20632 KB Output is correct
4 Runtime error 1067 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1487 ms 46380 KB Output is correct
2 Correct 1483 ms 26360 KB Output is correct
3 Correct 323 ms 19340 KB Output is correct
4 Runtime error 1061 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -