Submission #359357

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
359357	2021-01-27T00:17:25 Z	mjhmjh1104	Meteors (POI11_met)	C++17	100 / 100	2182 ms	41680 KB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

long long tree[300006];

long long query(int x) {
    x++;
    long long ret = 0;
    while (x > 0) {
        ret += tree[x];
        x -= x & -x;
    }
    return ret;
}

void update_fenwick(int x, long long v) {
    x++;
    while (x < 300006) {
        tree[x] += v;
        x += x & -x;
    }
}

void update(int l, int r, long long v) {
    update_fenwick(l, v);
    update_fenwick(r + 1, -v);
}

struct Query {
    int q;
    long long l;
    long long r;
    long long m;
};

int n, m, q;
long long p[300006];
vector<pair<pair<int, int>, long long>> updates;
vector<Query> queries;
vector<int> o[300006];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int t;
        scanf("%d", &t);
        o[t - 1].push_back(i);
    }
    for (int i = 0; i < n; i++) scanf("%lld", p + i);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int a, b;
        long long x;
        scanf("%d%d%lld", &a, &b, &x);
        a--, b--;
        updates.push_back({ { a, b }, x });
    }
    for (int i = 0; i < n; i++) queries.push_back(Query{ i, 0, 300002, 150000 });
    for (int t = 0; t < 20; t++) {
        sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
            return a.m < b.m;
        });
        fill(tree, tree + 300006, 0);
        int k = 0;
        for (int i = 0; i < q; i++) {
            while (k < n && i > queries[k].m) {
                long long sum = 0;
                for (auto &j: o[queries[k].q]) {
                    sum += query(j);
                    if (sum >= p[queries[k].q]) break;
                }
                if (sum >= p[queries[k].q]) queries[k].r = queries[k].m;
                else queries[k].l = queries[k].m + 1;
                queries[k].m = (queries[k].l + queries[k].r) / 2;
                k++;
            }
            if (updates[i].first.first <= updates[i].first.second) update(updates[i].first.first, updates[i].first.second, updates[i].second);
            else update(updates[i].first.first, m - 1, updates[i].second), update(0, updates[i].first.second, updates[i].second);
        }
        for (; k < n; k++) {
            long long sum = 0;
            for (auto &j: o[queries[k].q]) {
                sum += query(j);
                if (sum >= p[queries[k].q]) break;
            }
            if (sum >= p[queries[k].q]) queries[k].r = queries[k].m;
            else queries[k].l = queries[k].m + 1;
            queries[k].m = (queries[k].l + queries[k].r) / 2;
        }
    }
    sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
        return a.q < b.q;
    });
    for (auto &i: queries) {
        if (i.l > 300000) puts("NIE");
        else printf("%lld\n", i.l + 1);
    }
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
met.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~
met.cpp:51:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     for (int i = 0; i < n; i++) scanf("%lld", p + i);
      |                                 ~~~~~^~~~~~~~~~~~~~~
met.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
met.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |         scanf("%d%d%lld", &a, &b, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	9708 KB	Output is correct
2	Correct	14 ms	9708 KB	Output is correct
3	Correct	14 ms	9708 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	9708 KB	Output is correct
2	Correct	14 ms	9708 KB	Output is correct
3	Correct	15 ms	9836 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	11252 KB	Output is correct
2	Correct	235 ms	12384 KB	Output is correct
3	Correct	166 ms	12128 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	168 ms	11872 KB	Output is correct
2	Correct	198 ms	11876 KB	Output is correct
3	Correct	231 ms	12280 KB	Output is correct
4	Correct	64 ms	11108 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	11360 KB	Output is correct
2	Correct	243 ms	12520 KB	Output is correct
3	Correct	191 ms	10592 KB	Output is correct
4	Correct	158 ms	11944 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	168 ms	10848 KB	Output is correct
2	Correct	187 ms	11872 KB	Output is correct
3	Correct	136 ms	11124 KB	Output is correct
4	Correct	222 ms	12668 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1332 ms	26828 KB	Output is correct
2	Correct	678 ms	16852 KB	Output is correct
3	Correct	917 ms	16084 KB	Output is correct
4	Correct	2076 ms	40280 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1320 ms	26056 KB	Output is correct
2	Correct	699 ms	16852 KB	Output is correct
3	Correct	818 ms	16344 KB	Output is correct
4	Correct	2182 ms	41680 KB	Output is correct