Submission #681006

#	Time	Username	Problem	Language	Result	Execution time	Memory
681006		uylulu	Meteors (POI11_met)	C++17	74 / 100	1494 ms	65536 KiB

met

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13