oj.uz

답안 #380001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380001 2021-03-19T22:41:48 Z zecookiez Meteors (POI11_met) C++17
0 / 100
 51 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 3000005;
long long lim[MAXN], 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:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         while(pos < QT.size()) QT[pos] += V, pos += pos & -pos;
      |               ~~~~^~~~~~~~~~~
met.cpp: In function 'int main()':
met.cpp:42:59: warning: narrowing conversion of '((left1[i] + right1[i]) / 2)' from 'long long int' to 'int' [-Wnarrowing]
   42 |                 queries.push_back({(left1[i] + right1[i]) / 2, i});
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~^~~
met.cpp:48: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]
   48 |         while(j < queries.size() && -1 == queries[j][0]){
      |               ~~^~~~~~~~~~~~~~~~
met.cpp:60: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]
   60 |             while(j < queries.size() && i == queries[j][0]){
      |                   ~~^~~~~~~~~~~~~~~~
met.cpp:71: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]
   71 |         while(j < queries.size() && K == queries[j][0]){
      |               ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 51 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -