Submission #674361

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
674361	2022-12-23T18:56:58 Z	garam1732	Meteors (POI11_met)	C++14	74 / 100	3452 ms	33368 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]) 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	7388 KB	Output is correct
2	Correct	6 ms	7388 KB	Output is correct
3	Correct	7 ms	7348 KB	Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	10348 KB	Output is correct
2	Correct	362 ms	11448 KB	Output is correct
3	Correct	357 ms	10984 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	328 ms	10832 KB	Output is correct
2	Correct	343 ms	10848 KB	Output is correct
3	Correct	382 ms	11552 KB	Output is correct
4	Correct	101 ms	9928 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	171 ms	10364 KB	Output is correct
2	Correct	260 ms	11600 KB	Output is correct
3	Correct	144 ms	8560 KB	Output is correct
4	Correct	341 ms	11208 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	319 ms	10228 KB	Output is correct
2	Correct	312 ms	10956 KB	Output is correct
3	Correct	300 ms	10468 KB	Output is correct
4	Correct	374 ms	11724 KB	Output is correct

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3409 ms	33368 KB	Output is correct
2	Incorrect	1651 ms	28328 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3452 ms	32640 KB	Output is correct
2	Incorrect	1243 ms	26904 KB	Output isn't correct
3	Halted	0 ms	0 KB	-