oj.uz

답안 #862309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -