oj.uz

답안 #752265

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752265 2023-06-02T15:40:24 Z salmon Meteors (POI11_met) C++14
100 / 100
 4440 ms 48360 KB 
//meteors
#include <bits/stdc++.h>
using namespace std;

long long int st[1200100];
vector<int> place[300100];
int N,M,h;
int k;
int g[300100];
deque<pair<int,int>> q;
int s[300100];
int e[300100];
vector<vector<int>> days;
int ans[300100];
long long int con;

void build(int i, int s, int e){
    if(s == e){
        st[i] = 0;
        return;
    }

    st[i] = 0;

    build(i * 2,s,(s+e)/2);
    build(i*2+1,(s+e)/2+1, e);
}

void update(int i, int s, int e, int S, int E, int k){
    if(S <= s && e <= E){
        st[i] = st[i] + k;
        return;
    }

    int m = (s + e)/2;

    if(S <= m){
        update(i * 2, s, m,S,E,k);
    }
    if(m < E){
        update(i*2+1,m+1,e,S,E,k);
    }
}

long long int query(int i, int s, int e, int in){
    if(s == e){
        return st[i];
    }

    int m = (s + e)/2;

    if(in <= m){
        return min(con,st[i] + query(i*2, s, m, in));
    }
    else{
        return min(con,st[i] + query(i * 2+1,m + 1, e, in));
    }
}

int main(){
    con = 1000000000;

    scanf(" %d",&N);
    scanf(" %d",&M);

    for(int i = 1; i <= M; i++){
        scanf(" %d",&h);
        place[h].push_back(i);
    }

    for(int i = 1; i <= N; i++){
        scanf(" %d",&g[i]);
    }

    scanf(" %d",&k);

    for(int i = 1; i <= N; i++){
        s[i] = 1;
        e[i] = k + 1;
        q.push_back(make_pair((k+2)/2,i));
    }

    for(int i = 1; i <= k ; i++){
        int s,e,a;

        scanf(" %d",&s);
        scanf(" %d",&e);
        scanf(" %d",&a);

        vector<int> v = {s,e,a};
        days.push_back(v);
    }

    while(!q.empty()){

        sort(q.begin(),q.end());

        build(1,1,M);

        for(int i = 1; i <= k; i++){
            if(days[i-1][1] < days[i-1][0]){
                update(1,1,M,1,days[i-1][1],days[i-1][2]);
                update(1,1,M,days[i-1][0],M,days[i-1][2]);
            }
            else{
                update(1,1,M,days[i-1][0],days[i-1][1],days[i-1][2]);
            }

            while(!q.empty() && q.front().first == i){
                int j = q.front().second;
                q.pop_front();

                long long int some = 0;

                for(int k : place[j]){
                    some = some + query(1,1,M,k);
                }

                if(some >= g[j]) e[j] = (s[j] + e[j])/2;
                else s[j] = (s[j] + e[j])/2 + 1;

                if(e[j] != s[j]) q.push_back(make_pair((s[j] + e[j])/2,j));
                else ans[j] = s[j];
            }
        }
    }

    for(int i = 1; i <= N; i++){
        if(ans[i] == k + 1){
            printf("NIE\n");
        }
        else{
            printf("%d\n",ans[i]);
        }
    }
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
met.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
met.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
met.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf(" %d",&g[i]);
      |         ~~~~~^~~~~~~~~~~~~
met.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf(" %d",&k);
      |     ~~~~~^~~~~~~~~~
met.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf(" %d",&s);
      |         ~~~~~^~~~~~~~~~
met.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf(" %d",&e);
      |         ~~~~~^~~~~~~~~~
met.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 11544 KB Output is correct
2 Correct 375 ms 12408 KB Output is correct
3 Correct 408 ms 12012 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 11776 KB Output is correct
2 Correct 335 ms 11752 KB Output is correct
3 Correct 431 ms 12480 KB Output is correct
4 Correct 104 ms 9620 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 11604 KB Output is correct
2 Correct 235 ms 12576 KB Output is correct
3 Correct 141 ms 10148 KB Output is correct
4 Correct 384 ms 12216 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 307 ms 11404 KB Output is correct
2 Correct 287 ms 11752 KB Output is correct
3 Correct 293 ms 11496 KB Output is correct
4 Correct 349 ms 12692 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2699 ms 38528 KB Output is correct
2 Correct 1388 ms 33228 KB Output is correct
3 Correct 693 ms 21120 KB Output is correct
4 Correct 4440 ms 46364 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2787 ms 37988 KB Output is correct
2 Correct 1203 ms 33300 KB Output is correct
3 Correct 594 ms 18244 KB Output is correct
4 Correct 4390 ms 48360 KB Output is correct