답안 #869749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869749	2023-11-05T13:28:50 Z	riariti	Meteors (POI11_met)	C++17	100 / 100	4929 ms	65536 KB

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
using namespace std;
const ll N = 3e5 + 5;
const ll NN = 2e6 + 5;
const ll INF = -1e1;
const ll MOD = 1e9 + 7;
const ll LG = 18;
int z[N], x[N];
ll t[4 * N], b[N], c[N];
pair<int, int> seq[N];
set<int> MID[N];
vector<int> rg[N];
void build(int v, int l, int r) {
    t[v] = 0;
    if (l == r) {
        t[v] = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
}
void upd(int v, int l, int r, int ql, int qr, ll x) {
    if (ql <= l && r <= qr) {
        t[v] += x;
        return;
    }
    if (ql > r || qr < l)
        return;
    int mid = (l + r) / 2;
    upd(v + v, l, mid, ql, qr, x);
    upd(v + v + 1, mid + 1, r, ql, qr, x);
}
ll get(int v, int l, int r, int pos, ll sum) {
    sum += t[v];
    if (l == r)
        return sum;
    int mid = (l + r) / 2;
    if (pos <= mid)
        return get(v + v, l, mid, pos, sum);
    else
        return get(v + v + 1, mid + 1, r, pos, sum);
}
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u;
        cin >> u;
        rg[u].pb(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> z[i] >> x[i] >> c[i];
    }
    for (int i = 1; i <= n; i++) {
        seq[i] = {1, q};
    }
    int tt = 19;
    while (tt--) {
        for (int i = 1; i <= n; i++) {
            int md = (seq[i].F + seq[i].S) / 2;
            MID[md].insert(i);
        }
        build(1, 1, m);
        for (int i = 1; i <= q; i++) {
            if (z[i] > x[i]) {
                upd(1, 1, m, 1, x[i], c[i]);
                upd(1, 1, m, z[i], m, c[i]);
            } else {
                upd(1, 1, m, z[i], x[i], c[i]);
            }
            for (int to : MID[i]) {
                ll sum = 0;
                for (int d : rg[to]) {
                    sum += get(1, 1, m, d, 0);
                    if (sum >= b[to])
                        break;
                }
                if (sum >= b[to]) {
                    seq[to].S = i;
                } else {
                    seq[to].F = i + 1;
                }
            }
        }
        for (int i = 1; i <= q; i++) {
            MID[i].clear();
        }
    }
    for (int i = 1; i <= n; i++) {
        if (seq[i].F <= q) {
            cout << seq[i].F << '\n';
        } else {
            cout << "NIE\n";
        }
    }
}
main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //    freopen("input.txt","r",stdin);
    //    freopen("output.txt","w",stdout);
    ll abd = 1;
    // cin >> abd;
    for (ll i = 1; i <= abd; i++) {
        //        cout << "Case " << i << ":\n";
        solve();
    }
}

Compilation message

met.cpp:108:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  108 | main() {
      | ^~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	31436 KB	Output is correct
2	Correct	11 ms	31456 KB	Output is correct
3	Correct	10 ms	31324 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	31324 KB	Output is correct
2	Correct	10 ms	31364 KB	Output is correct
3	Correct	11 ms	31324 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	282 ms	33972 KB	Output is correct
2	Correct	399 ms	35500 KB	Output is correct
3	Correct	364 ms	34640 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	349 ms	34392 KB	Output is correct
2	Correct	341 ms	34144 KB	Output is correct
3	Correct	414 ms	35312 KB	Output is correct
4	Correct	112 ms	34652 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	33880 KB	Output is correct
2	Correct	278 ms	35396 KB	Output is correct
3	Correct	147 ms	31320 KB	Output is correct
4	Correct	363 ms	34836 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	314 ms	33776 KB	Output is correct
2	Correct	302 ms	34584 KB	Output is correct
3	Correct	316 ms	33848 KB	Output is correct
4	Correct	401 ms	35432 KB	Output is correct

Subtask #7
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3044 ms	49244 KB	Output is correct
2	Correct	1129 ms	41688 KB	Output is correct
3	Correct	722 ms	34296 KB	Output is correct
4	Correct	4761 ms	65292 KB	Output is correct

Subtask #8
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3028 ms	48212 KB	Output is correct
2	Correct	774 ms	41432 KB	Output is correct
3	Correct	582 ms	34696 KB	Output is correct
4	Correct	4929 ms	65536 KB	Output is correct