Submission #862309

#	Time	Username	Problem	Language	Result	Execution time	Memory
862309		city	새로운 문제 (POI11_met)	C++14	87 / 100	1565 ms	63888 KiB

met

#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 (stderr)

met.cpp: In function 'int main()':
met.cpp:100:9: warning: unused variable 'temp' [-Wunused-variable]
  100 |     int temp=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: 13 / 13
• Subtask 8: 0 / 13