제출 #379999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379999		zecookiez	새로운 문제 (POI11_met)	C++17	74 / 100	1281 ms	28424 KiB

met

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13