Submission #862309

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
862309	2023-10-18T03:37:11 Z	city	Meteors (POI11_met)	C++14	87 / 100	1565 ms	63888 KB

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <list>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <unordered_set>
using namespace std;
typedef long long ll;

const int MAX_N=300005;
const int INF=1e9;
const ll MOD=1000000007;

typedef struct starfall{
    int l,r,a;
}starfall;

int n,m,t,q;
vector<int> own[MAX_N];
int goal[MAX_N], low[MAX_N], high[MAX_N];
starfall fall[MAX_N];
int arr[MAX_N], tree[MAX_N*2];

void init(){
    fill(arr, arr+MAX_N, 0);
    fill(tree, tree+2*MAX_N, 0);
}

int len;

// [l, r)
int query(int l, int r){
    int res=0;
    for(l+=len, r+=len; l<r; l>>=1, r>>=1){
        if(l&1){res+=tree[l++];}
        if(r&1){res+=tree[--r];}
    }
    return res;
}

void update(int pos, int val){
    for(tree[pos+=len]=val; pos>1; pos>>=1){ tree[pos>>1]=tree[pos]+tree[pos^1]; }
}

// day를 진행시 상태
void make_state(int d){
    int l,r,a;
    l=fall[d].l; r=fall[d].r; a=fall[d].a;
    if(l<=r){
        arr[l]+=a; arr[r+1]-=a;
        update(l, arr[l]);
        update(r+1, arr[r+1]);
    }
    // l > r
    else{
        arr[l]+=a; arr[0]+=a; arr[r+1]-=a;
        update(0, arr[0]);
        update(l, arr[l]);
        update(r+1, arr[r+1]);
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for(auto &i : fall){
        i={0,0,0};
    }
    cin>>n>>m;
    len=m+1;
    // 입력받은 국가가 i번 구역을 소유한다
    for(int i=0;i<m;i++){
        cin>>t;
        own[t-1].push_back(i);
    }
    // 각 국가의 목표치
    for(int i=0;i<n;i++){
        cin>>goal[i];
    }
    cin>>q;
    // i일의 쿼리
    for(int i=1;i<=q;i++){
        int l,r,a;
        cin>>l>>r>>a;
        fall[i]={l-1,r-1,a};
    }
    fill(low, low+MAX_N, 1);
    fill(high, high+MAX_N, q);
    vector<int> mid[MAX_N];
    int check, cnt;
    int temp=0;
    while(true){
        init();

        /*temp++;
        cout<<"iteration "<<temp<<"\n";
        for(int i=0;i<n;i++){
            cout<<"nation "<<i<<", ";
            cout<<low[i]<<" "<<high[i]<<"\n";
        }*/

        check=0;
        for(auto &i : mid){i.clear();}
        for(int i=0;i<n;i++){
            if(low[i]<=high[i]){
                check=1;
                mid[(low[i]+high[i])/2].push_back(i);
            }
        }
        if(check==0){break;}

        for(int day=1;day<=q;day++){
            make_state(day);
            // mid가 day인 국가에 대한 쿼리들을 처리

            for(int nation:mid[day]){
                cnt=0;
                //cout<<mid<<" ";
                for(int r:own[nation]){
                    cnt+=query(0, r+1);
                    //cout<<query(0, r+1)<<" ";
                    if(cnt>=goal[nation]){break;}
                }
                // 더 적은 day로도 가능할 수 있다. 즉 줄여 본다
                if(cnt>=goal[nation]){high[nation]=day-1;}
                else{low[nation]=day+1;}
            }
        }
    }
    for(int i=0;i<n;i++){
        if(low[i] > q){cout<<"NIE";}
        else{
            cout<<low[i];
        }
        if(i!=n-1){cout<<"\n";}
    }

    return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:100:9: warning: unused variable 'temp' [-Wunused-variable]
  100 |     int temp=0;
      |         ^~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	24924 KB	Output is correct
2	Correct	13 ms	24924 KB	Output is correct
3	Correct	13 ms	25148 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	24924 KB	Output is correct
2	Correct	13 ms	24924 KB	Output is correct
3	Correct	13 ms	25180 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	26932 KB	Output is correct
2	Correct	155 ms	28788 KB	Output is correct
3	Correct	123 ms	28408 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	27732 KB	Output is correct
2	Correct	132 ms	27768 KB	Output is correct
3	Correct	121 ms	28752 KB	Output is correct
4	Correct	59 ms	26964 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	26884 KB	Output is correct
2	Correct	116 ms	29364 KB	Output is correct
3	Correct	41 ms	25732 KB	Output is correct
4	Correct	120 ms	28704 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	26456 KB	Output is correct
2	Correct	95 ms	27984 KB	Output is correct
3	Correct	97 ms	26676 KB	Output is correct
4	Correct	138 ms	29976 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1026 ms	45228 KB	Output is correct
2	Correct	336 ms	34248 KB	Output is correct
3	Correct	147 ms	27492 KB	Output is correct
4	Correct	1565 ms	63888 KB	Output is correct

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1042 ms	44212 KB	Output is correct
2	Correct	393 ms	32772 KB	Output is correct
3	Incorrect	128 ms	28504 KB	Output isn't correct
4	Halted	0 ms	0 KB	-