oj.uz

답안 #622271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
622271 2022-08-04T05:32:57 Z jame0313 Meteors (POI11_met) C++17
74 / 100
 1816 ms 32944 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
using tii = tuple<int, int, int>;
// and so on
int arr[300001];
ll goal[300001];
vector<vector<int> > lst, listeners;
vector<tii> Event, query;
struct bit {
    ll tree[1 << 21], siz;
    void init(int x) {
        for (siz = 1; siz < x; siz <<= 1)
            ;
    }
    void clear() {
        for (int i = 0; i <= siz; i++) tree[i] = 0;
    }
    void add(int pos, ll x) {
        while (pos <= siz) {
            tree[pos] += x;
            pos += (pos & -pos);
        }
    }
    ll sum(int pos) {
        ll ret = 0;
        while (pos) {
            ret += tree[pos];
            pos &= (pos - 1);
        }
        return ret;
    }
} Tree;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int Q, N, M;
    cin >> Q >> N;
    lst.resize(Q + 1);
    Tree.init(N + 5);
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        lst[arr[i]].push_back(i);
    }
    for (int i = 1; i <= Q; i++) {
        cin >> goal[i];
    }
    cin >> M;
    listeners.resize(M + 1);
    for (int i = 0; i < M; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        Event.push_back({l, r, c});
    }
    for (int i = 0; i <= Q; i++) {
        query.push_back({0, M-1, 0});
    }
    for (int t = 0; t < 32; t++) {
        Tree.clear();
        for (int i = 1; i <= Q; i++) {
            auto& [l, r, m] = query[i];
            if (l <= r) {
                m = (l + r) >> 1;
                listeners[m].push_back(i);
            }
        }
        for (int i = 0; i < M; i++) {
            auto [l, r, c] = Event[i];
            if(l<=r){
                Tree.add(l, c);
                Tree.add(r+1, -c);
            }
            else{
                Tree.add(l, c);
                Tree.add(N+1, -c);
                Tree.add(1, c);
                Tree.add(r+1, -c);
            }
            for (int j : listeners[i]) {
                auto& [l, r, m] = query[j];
                ll sum = 0;
                for (int k : lst[j]) sum += Tree.sum(k);
                if (sum < goal[j]) {
                    l = m + 1;
                } else
                    r = m - 1;
            }
            listeners[i].clear();
        }
    }
    for (int i = 1; i <= Q; i++) {
        auto [l,r,m] = query[i];
        if(l == M) cout<<"NIE\n";
        else cout<<l+1<<'\n';
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 3792 KB Output is correct
2 Correct 201 ms 6416 KB Output is correct
3 Correct 152 ms 5552 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 4956 KB Output is correct
2 Correct 160 ms 4972 KB Output is correct
3 Correct 200 ms 6428 KB Output is correct
4 Correct 40 ms 3540 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 4216 KB Output is correct
2 Correct 169 ms 6976 KB Output is correct
3 Correct 88 ms 2384 KB Output is correct
4 Correct 133 ms 6232 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 3268 KB Output is correct
2 Correct 178 ms 4940 KB Output is correct
3 Correct 102 ms 3524 KB Output is correct
4 Correct 219 ms 7732 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1662 ms 32944 KB Output is correct
2 Incorrect 1816 ms 17816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1695 ms 31564 KB Output is correct
2 Incorrect 1208 ms 17716 KB Output isn't correct
3 Halted 0 ms 0 KB -