oj.uz

답안 #674362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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