답안 #1104932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104932	2024-10-24T18:46:42 Z	Irate	Meteors (POI11_met)	C++17	100 / 100	786 ms	28788 KB

#include<cstdio>
#include<vector>
using namespace std;
const int mxN = 3e5 + 5;
long long fen[mxN];
vector<int> pos[mxN];
int sectors[mxN], need[mxN], ans[mxN];
int P = -1, n, m, q;
void Update(int pos, int val){
    while(pos < mxN){
        fen[pos] += val;
        pos += (pos & -pos);
    }
}
long long Sum(int pos){
    long long sum = 0;
    while(pos > 0){
        sum += fen[pos];
        pos -= (pos & -pos);
    }
    return sum;
}
struct Query{
    int l, r, a;
} queries[mxN];
void f(int l, int r, vector<int>&exist){
    int mid = (l + r) / 2;
    if(mid == q){
        for(int &sector : exist){
            ans[sector] = -1;       
        }
        return;
    }
    if(l == r){
        for(int &sector : exist){
            ans[sector] = l;
        }
        return;
    }
    while(P + 1 <= mid){
        P++;
        int l = queries[P].l, r = queries[P].r, a = queries[P].a;
        if(l <= r){
            Update(l, a);
            Update(r + 1, -a);
        }
        else{
            Update(l, a);
            Update(1, a);
            Update(r + 1, -a);
        }
    }
    while(P - 1 >= mid){
        int l = queries[P].l, r = queries[P].r, a = queries[P].a;
        if(l <= r){
            Update(l, -a);
            Update(r + 1, a);
        }
        else{
            Update(l, -a);
            Update(1, -a);
            Update(r + 1, a);
        }
        P--;
    }
    vector<int>left, right;
    for(int &sector : exist){
        long long tot = 0;
        for(int &i : pos[sector]){
            tot += Sum(i);
            if(tot >= need[sector]){
                break;
            }
        }
        if(tot >= need[sector]){
            left.push_back(sector);
        }
        else{
            right.push_back(sector);
        }
    }
    f(l, mid, left);
    f(mid + 1, r, right);
}
int main(){
    scanf("%d%d", &m, &n);
    for(int i = 1;i <= n;++i){
        scanf("%d", &sectors[i]);
        pos[sectors[i]].push_back(i);
    }
    vector<int>exist;
    for(int i = 1;i <= m;++i){
        scanf("%d", &need[i]);
        exist.push_back(i);
    }
    scanf("%d", &q);
    for(int i = 0;i < q;++i){
        int l, r, a;
        scanf("%d%d%d", &l, &r, &a);
        queries[i] = {l, r, a};
    }
    f(0, q, exist);
    for(int i = 1;i <= m;++i){
        if(ans[i] < 0){
            printf("NIE\n");
        }
        else{
            printf("%d\n", ans[i] + 1);
        }
    }
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d%d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
met.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%d", &sectors[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
met.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%d", &need[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
met.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
met.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d%d%d", &l, &r, &a);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	48 ms	13904 KB	Output is correct
2	Correct	96 ms	15688 KB	Output is correct
3	Correct	63 ms	14020 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	70 ms	13904 KB	Output is correct
2	Correct	77 ms	13896 KB	Output is correct
3	Correct	92 ms	14920 KB	Output is correct
4	Correct	16 ms	13904 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	13788 KB	Output is correct
2	Correct	102 ms	15176 KB	Output is correct
3	Correct	60 ms	13384 KB	Output is correct
4	Correct	66 ms	14176 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	13648 KB	Output is correct
2	Correct	80 ms	13904 KB	Output is correct
3	Correct	52 ms	13656 KB	Output is correct
4	Correct	82 ms	14676 KB	Output is correct

Subtask #7
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	601 ms	25752 KB	Output is correct
2	Correct	425 ms	17996 KB	Output is correct
3	Correct	351 ms	15856 KB	Output is correct
4	Correct	786 ms	27084 KB	Output is correct

Subtask #8
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	635 ms	24128 KB	Output is correct
2	Correct	387 ms	18120 KB	Output is correct
3	Correct	243 ms	17744 KB	Output is correct
4	Correct	768 ms	28788 KB	Output is correct