Submission #674362

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
674362	2022-12-23T19:29:51 Z	garam1732	Meteors (POI11_met)	C++14	100 / 100	4347 ms	40632 KB

#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

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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	7380 KB	Output is correct
2	Correct	6 ms	7380 KB	Output is correct
3	Correct	7 ms	7380 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	7348 KB	Output is correct
2	Correct	6 ms	7380 KB	Output is correct
3	Correct	7 ms	7380 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	9468 KB	Output is correct
2	Correct	364 ms	10300 KB	Output is correct
3	Correct	337 ms	9960 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	330 ms	9804 KB	Output is correct
2	Correct	321 ms	9764 KB	Output is correct
3	Correct	349 ms	10316 KB	Output is correct
4	Correct	90 ms	9468 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	9556 KB	Output is correct
2	Correct	264 ms	10400 KB	Output is correct
3	Correct	133 ms	7928 KB	Output is correct
4	Correct	331 ms	10128 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	297 ms	9324 KB	Output is correct
2	Correct	269 ms	9752 KB	Output is correct
3	Correct	304 ms	9420 KB	Output is correct
4	Correct	365 ms	10564 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3458 ms	25524 KB	Output is correct
2	Correct	1180 ms	20448 KB	Output is correct
3	Correct	725 ms	12748 KB	Output is correct
4	Correct	4347 ms	38716 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3419 ms	25012 KB	Output is correct
2	Correct	832 ms	20552 KB	Output is correct
3	Correct	583 ms	13256 KB	Output is correct
4	Correct	4269 ms	40632 KB	Output is correct