Submission #380003

#	Time	Username	Problem	Language	Result	Execution time	Memory
380003		zecookiez	Meteors (POI11_met)	Pypy 2	0 / 100	41 ms	20168 KiB

met

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 600005;
long long lim[MAXN], left1[MAXN], right1[MAXN], qu[MAXN][3];
vector<int> id[MAXN];
 
int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, M; cin >> N >> M;
    for(int a, i = 1; i <= M; ++i) cin >> a, id[a].push_back(i);
    for(int i = 1; i <= N; ++i) cin >> lim[i];
    vector<long long> QT(M + 2, 0);
    auto apply  = [&](int pos, long long V){
        assert(pos != 0);
        while(pos < QT.size()) QT[pos] += V, pos += pos & -pos;
    };
    auto update = [&](int L, int R, long long V){
        if(M == 1){
            QT[1] += V; return;
        }
        if(L <= R){
            apply(L, V); apply(R + 1, -V); return;
        }
        apply(L, V); apply(1, V); apply(R + 1, -V);
    };
    auto point = [&](int pos){
        if(M == 1) return QT[1];
        long long tot = 0;
        while(pos) tot += QT[pos], pos &= pos - 1;
        return tot;
    };
 
    int K; cin >> K;
    for(int i = 0; i < K; ++i) cin >> qu[i][0] >> qu[i][1] >> qu[i][2];
    for(int i = 1; i <= N; ++i) left1[i] = -1, right1[i] = K;
 
    while(true){
        vector<array<int, 2>> queries = {};
        for(int i = 1; i <= N; ++i){
            if(right1[i] - left1[i] > 1){
                queries.push_back({(left1[i] + right1[i]) / 2, i});
            }
        }
        if(queries.empty()) break;
        sort(queries.begin(), queries.end());
        fill(QT.begin(), QT.end(), 0); int j = 0;
        while(j < queries.size() && -1 == queries[j][0]){
            int k = queries[j][1];
            long long tot = 0;
            for(int a : id[k]){
                tot += point(a);
            }
            if(tot >= lim[k]) right1[k] = -1;
            else left1[k] = -1;
            ++j;
        }
        for(int i = 0; i < K; ++i){
            update(qu[i][0], qu[i][1], qu[i][2]);
            while(j < queries.size() && i == queries[j][0]){
                int k = queries[j][1];
                long long tot = 0;
                for(int a : id[k]){
                    tot += point(a);
                }
                if(tot >= lim[k]) right1[k] = i;
                else left1[k] = i;
                ++j;
            }
        }
        while(j < queries.size() && K == queries[j][0]){
            int k = queries[j][1];
            long long tot = 0;
            for(int a : id[k]){
                tot += point(a);
            }
            if(tot >= lim[k]) right1[k] = K;
            else left1[k] = K;
            ++j;
        }
    }
    for(int i = 1; i <= N; ++i){
        if(right1[i] == K) cout << "NIE\n";
        else cout << right1[i] + 1 << '\n';
    }
 
 
    return 0;
}

Compilation message (stderr)

File "met.py", line 2
    using namespace std;
         ^
SyntaxError: invalid syntax

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13