oj.uz

답안 #674361

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

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

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

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

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

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

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

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

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