Submission #674362

#	Time	Username	Problem	Language	Result	Execution time	Memory
674362		garam1732	Meteors (POI11_met)	C++14	100 / 100	4347 ms	40632 KiB

met

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define blank " "
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 300300;
const int MOD = 1e9+7;

vector<int> idx[MAXN];
vector<ll> tree;
vector<pi> v;
pii query[MAXN];
pi bin[MAXN];
int goal[MAXN];

void update(int node, int s, int e, int l, int r, int v) {
    if(e < l || r < s) return;
    if(l <= s && e <= r) {
        tree[node] += v;
        return;
    }

    int mid = s+e>>1;
    update(node<<1, s, mid, l, r, v); update(node<<1|1, mid+1, e, l, r, v);
}

ll solve(int node, int s, int e, int x) {
    if(e < x || x < s) return 0;

    ll res = tree[node];
    if(s != e) {
        int mid = s+e>>1;
        res += solve(node<<1, s, mid, x) + solve(node<<1|1, mid+1, e, x);
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int x; cin >> x;
        idx[x].push_back(i);
    }

    for(int i = 1; i <= n; i++) cin >> goal[i];

    int q; cin >> q;
    for(int i = 1; i <= q; i++) cin >> query[i].ff.ff >> query[i].ff.ss >> query[i].ss;

    for(int i = 1; i <= n; i++) bin[i] = pi(1, q+1);

    while(true) {
        v.clear();
        for(int i = 1; i <= n; i++) v.push_back(pi(bin[i].ff+bin[i].ss>>1, i));
        sort(v.begin(), v.end());

        tree.clear();
        int h = (int)ceil(log2(m));
        tree.resize(1 << (h+1));

        int piv = 0, cnt = 0;
        for(int i = 1; i <= q; i++) {
            if(query[i].ff.ff <= query[i].ff.ss) update(1, 1, m, query[i].ff.ff, query[i].ff.ss, query[i].ss);
            else {
                update(1, 1, m, query[i].ff.ff, m, query[i].ss);
                update(1, 1, m, 1, query[i].ff.ss, query[i].ss);
            }

            while(piv < v.size() && v[piv].ff == i) {
                ll res = 0; int x = v[piv].ss;
                for(int z : idx[x]) {
                    res += solve(1, 1, m, z);
                    if(res >= goal[x]) break;
                }

                if(res < goal[x]) bin[x].ff = i+1;
                else bin[x].ss = i;

                if(bin[x].ff < bin[x].ss) cnt++;
                piv++;
            }
        }

        if(!cnt) break;
    }

    for(int i = 1; i <= n; i++) {
        if(bin[i].ff == q+1) cout << "NIE" << endl;
        else cout << bin[i].ff << endl;
    }
}

Compilation message (stderr)

met.cpp: In function 'void update(int, int, int, int, int, int)':
met.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = s+e>>1;
      |               ~^~
met.cpp: In function 'll solve(int, int, int, int)':
met.cpp:39:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid = s+e>>1;
      |                   ~^~
met.cpp: In function 'int main()':
met.cpp:66:61: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         for(int i = 1; i <= n; i++) v.push_back(pi(bin[i].ff+bin[i].ss>>1, i));
      |                                                             ^
met.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             while(piv < v.size() && v[piv].ff == i) {
      |                   ~~~~^~~~~~~~~~

• 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: 13 / 13
• Subtask 8: 13 / 13