제출 #752206

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752206		salmon	새로운 문제 (POI11_met)	C++14	61 / 100	323 ms	65536 KiB

met

//meteors
#include <bits/stdc++.h>
using namespace std;

vector<long long int> st;
vector<int> l;
vector<int> r;
vector<int> place[300100];
int N,M,h;
int it;
int k;
int root[300100];
int g[300100];

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

        st.push_back(st[c]);
        l.push_back(0);
        r.push_back(0);
        it++;

        int m = (s + e)/2;
        int lef = l[c];
        int righ = r[c];

        if(S <= m){
            lef = it;
            update(it, s, m, S, E, l[c], k);
        }
        if(E > m){
            righ = it;
            update(it,m + 1,e, S, E,r[c],k);
        }

        l[i] = lef;
        r[i] = righ;

        return;
    }
    else{
        if(S <= s || e <= E){
            st.push_back(st[c] + k);
            l.push_back(l[c]);
            r.push_back(r[c]);
            it++;
            return;
        }

        st.push_back(st[c]);
        l.push_back(0);
        r.push_back(0);
        it++;

        int m = (s + e)/2;
        int lef = l[c];
        int righ = r[c];

        if(S <= m || s <= E){
            lef = it;
            update(it, s, m, S, E, l[c], k);
        }
        if(m < E  || S <= e){
            righ = it;
            update(it,m + 1,e, S, E,r[c],k);
        }

        l[i] = lef;
        r[i] = righ;

        return;
    }
}

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

    if(in <= (s+e)/2){
        return st[i] + query(l[i], s, (s+e)/2,in);
    }
    else{
        return st[i] + query(r[i],(s+e)/2+1,e,in);
    }
}

int main(){

    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]);
    }

    it = 0;
    st.push_back(0);
    l.push_back(0);
    r.push_back(0);
    it++;

    scanf(" %d",&k);

    root[0] = 0;

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

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

        root[i] = it;
        update(it, 1, M, s, e, root[i - 1], a);
    }

    for(int i = 1; i <= N; i++){
        int s = 1;
        int e = k + 1;
        int m;

        while(s != e){
            m = (s+e)/2;

            long long int some = 0;

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

            if(some >= g[i]){
                e = m;
            }
            else{
                s = m + 1;
            }
        }

        if(s == k + 1){
            printf("NIE\n");
        }
        else{
            printf("%d\n",s);
        }
    }

    /*for(int j = 0; j <= k; j++){
        for(int i = 1; i <= M; i++){
            printf("%lld ",query(root[j],1,M,i));
        }
        printf("\n");
    }*/
}

컴파일 시 표준 에러 (stderr) 메시지

met.cpp: In function 'int main()':
met.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
met.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
met.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
met.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf(" %d",&g[i]);
      |         ~~~~~^~~~~~~~~~~~~
met.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     scanf(" %d",&k);
      |     ~~~~~^~~~~~~~~~
met.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf(" %d",&s);
      |         ~~~~~^~~~~~~~~~
met.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         scanf(" %d",&e);
      |         ~~~~~^~~~~~~~~~
met.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13