oj.uz

답안 #379999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379999 2021-03-19T22:39:57 Z zecookiez Meteors (POI11_met) C++17
74 / 100
 1281 ms 28424 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
long long lim[MAXN];
int left1[MAXN], right1[MAXN], qu[MAXN][3];
vector<int> id[MAXN];

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, M; cin >> N >> M;
    for(int a, i = 1; i <= M; ++i) cin >> a, id[a].push_back(i);
    for(int i = 1; i <= N; ++i) cin >> lim[i];
    vector<long long> QT(M + 2, 0);
    auto apply  = [&](int pos, long long V){
        assert(pos != 0);
        while(pos < QT.size()) QT[pos] += V, pos += pos & -pos;
    };
    auto update = [&](int L, int R, long long V){
        if(M == 1){
            QT[1] += V; return;
        }
        if(L <= R){
            apply(L, V); apply(R + 1, -V); return;
        }
        apply(L, V); apply(1, V); apply(R + 1, -V);
    };
    auto point = [&](int pos){
        if(M == 1) return QT[1];
        long long tot = 0;
        while(pos) tot += QT[pos], pos &= pos - 1;
        return tot;
    };

    int K; cin >> K;
    for(int i = 0; i < K; ++i) cin >> qu[i][0] >> qu[i][1] >> qu[i][2];
    for(int i = 1; i <= N; ++i) left1[i] = -1, right1[i] = K;

    while(true){
        vector<array<int, 2>> queries = {};
        for(int i = 1; i <= N; ++i){
            if(right1[i] - left1[i] > 1){
                queries.push_back({(left1[i] + right1[i]) / 2, i});
            }
        }
        if(queries.empty()) break;
        sort(queries.begin(), queries.end());
        fill(QT.begin(), QT.end(), 0); int j = 0;
        while(j < queries.size() && -1 == queries[j][0]){
            int k = queries[j][1];
            long long tot = 0;
            for(int a : id[k]){
                tot += point(a);
            }
            if(tot >= lim[k]) right1[k] = -1;
            else left1[k] = -1;
            ++j;
        }
        for(int i = 0; i < K; ++i){
            update(qu[i][0], qu[i][1], qu[i][2]);
            while(j < queries.size() && i == queries[j][0]){
                int k = queries[j][1];
                long long tot = 0;
                for(int a : id[k]){
                    tot += point(a);
                }
                if(tot >= lim[k]) right1[k] = i;
                else left1[k] = i;
                ++j;
            }
        }
        while(j < queries.size() && K == queries[j][0]){
            int k = queries[j][1];
            long long tot = 0;
            for(int a : id[k]){
                tot += point(a);
            }
            if(tot >= lim[k]) right1[k] = K;
            else left1[k] = K;
            ++j;
        }
    }
    for(int i = 1; i <= N; ++i){
        if(right1[i] == K) cout << "NIE\n";
        else cout << right1[i] + 1 << '\n';
    }


    return 0;
}

Compilation message

met.cpp: In lambda function:
met.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while(pos < QT.size()) QT[pos] += V, pos += pos & -pos;
      |               ~~~~^~~~~~~~~~~
met.cpp: In function 'int main()':
met.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while(j < queries.size() && -1 == queries[j][0]){
      |               ~~^~~~~~~~~~~~~~~~
met.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             while(j < queries.size() && i == queries[j][0]){
      |                   ~~^~~~~~~~~~~~~~~~
met.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while(j < queries.size() && K == queries[j][0]){
      |               ~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 9836 KB Output is correct
2 Correct 141 ms 11124 KB Output is correct
3 Correct 121 ms 10468 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 10396 KB Output is correct
2 Correct 114 ms 10524 KB Output is correct
3 Correct 166 ms 11256 KB Output is correct
4 Correct 54 ms 9404 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 9860 KB Output is correct
2 Correct 137 ms 11272 KB Output is correct
3 Correct 50 ms 8556 KB Output is correct
4 Correct 130 ms 10900 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 9708 KB Output is correct
2 Correct 118 ms 10412 KB Output is correct
3 Correct 81 ms 9964 KB Output is correct
4 Correct 172 ms 11480 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1281 ms 28424 KB Output is correct
2 Incorrect 715 ms 22520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1243 ms 27592 KB Output is correct
2 Incorrect 666 ms 20980 KB Output isn't correct
3 Halted 0 ms 0 KB -