oj.uz

Submission #680997

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

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

const int N = 3e5 + 5;

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] += 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] += 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 11 ms 14420 KB Output is correct
2 Correct 9 ms 14456 KB Output is correct
3 Correct 10 ms 14532 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 9 ms 14476 KB Output is correct
3 Correct 10 ms 14640 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17472 KB Output is correct
2 Correct 184 ms 20796 KB Output is correct
3 Correct 168 ms 19792 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 18996 KB Output is correct
2 Correct 147 ms 18960 KB Output is correct
3 Correct 207 ms 21272 KB Output is correct
4 Correct 38 ms 18108 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17884 KB Output is correct
2 Correct 159 ms 21408 KB Output is correct
3 Correct 91 ms 15696 KB Output is correct
4 Correct 131 ms 20508 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 16636 KB Output is correct
2 Correct 168 ms 18856 KB Output is correct
3 Correct 122 ms 17116 KB Output is correct
4 Correct 190 ms 22620 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 48596 KB Output is correct
2 Incorrect 1468 ms 26328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1708 ms 46376 KB Output is correct
2 Incorrect 1503 ms 26324 KB Output isn't correct
3 Halted 0 ms 0 KB -