oj.uz

답안 #477741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477741 2021-10-03T11:09:59 Z mat_v Meteors (POI11_met) C++14
74 / 100
 1045 ms 37032 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
using namespace std;
typedef long long ll;

int n,m,q;
int niz[300005];
vector<int> drz[300005];
int targ[300005];
int le[300005];
int ri[300005];
ll val[300005];

vector<int> buc[300005];
int l[300005];
int r[300005];
int bucs[300005];
int ans[300005];


ll bit[300005];
void upd(int x, int val){
    while(x <= n){
        bit[x] += val;
        x += (x&-x);
    }
}
ll kveri(int x){
    ll res = 0;
    while(x > 0){
        res += bit[x];
        x -= (x&-x);
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> m >> n;
    ff(i,1,n){
        cin >> niz[i];
        drz[niz[i]].pb(i);
    }
    ff(i,1,m)cin >> targ[i];
    cin >> q;
    ff(i,1,q)cin >> le[i] >> ri[i] >> val[i];
    int t = q;
    ff(i,1,t){
    }
    ff(i,1,m){
        l[i] = 1;
        r[i] = q;
        bucs[i] = (1+q)/2;
        ans[i] = -1;
    }
    while(1){
        bool ch = 0;
        fill(bit, bit + 300001, 0);
        ff(i,1,q)buc[i].clear();
        ff(i,1,m){
            if(l[i] <= r[i]){
                ch = 1;
                buc[(l[i] + r[i]) / 2].pb(i);
            }
        }
        if(!ch)break;
        ff(i,1,q){
            if(le[i] > ri[i]){
                upd(le[i], val[i]);
                upd(1, val[i]);
                upd(ri[i] + 1, -val[i]);
            }
            else{
                upd(le[i], val[i]);
                upd(ri[i] + 1, -val[i]);
            }
            for(auto c:buc[i]){
                ll sm = 0;
                for(auto tt:drz[c])sm += kveri(tt);
                if(sm >= targ[c]){
                    ans[c] = i;
                    r[c] = i-1;
                }
                else l[c] = i+1;
            }
        }
    }
    ff(i,1,m){
        if(ans[i] == -1)cout << "NIE\n";
        else cout << ans[i] << "\n";
    }

    return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:43:5: note: in expansion of macro 'ff'
   43 |     ff(i,1,n){
      |     ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:47:5: note: in expansion of macro 'ff'
   47 |     ff(i,1,m)cin >> targ[i];
      |     ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:49:5: note: in expansion of macro 'ff'
   49 |     ff(i,1,q)cin >> le[i] >> ri[i] >> val[i];
      |     ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:51:5: note: in expansion of macro 'ff'
   51 |     ff(i,1,t){
      |     ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:53:5: note: in expansion of macro 'ff'
   53 |     ff(i,1,m){
      |     ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:62:9: note: in expansion of macro 'ff'
   62 |         ff(i,1,q)buc[i].clear();
      |         ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:63:9: note: in expansion of macro 'ff'
   63 |         ff(i,1,m){
      |         ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:70:9: note: in expansion of macro 'ff'
   70 |         ff(i,1,q){
      |         ^~
met.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
met.cpp:91:5: note: in expansion of macro 'ff'
   91 |     ff(i,1,m){
      |     ^~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16844 KB Output is correct
2 Correct 12 ms 16876 KB Output is correct
3 Correct 11 ms 16844 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16844 KB Output is correct
2 Correct 11 ms 16844 KB Output is correct
3 Correct 11 ms 16876 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 18628 KB Output is correct
2 Correct 121 ms 21976 KB Output is correct
3 Correct 106 ms 21360 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 19652 KB Output is correct
2 Correct 110 ms 20720 KB Output is correct
3 Correct 135 ms 22088 KB Output is correct
4 Correct 42 ms 19396 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 19020 KB Output is correct
2 Correct 109 ms 22516 KB Output is correct
3 Correct 54 ms 18228 KB Output is correct
4 Correct 116 ms 21748 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 18016 KB Output is correct
2 Correct 111 ms 20932 KB Output is correct
3 Correct 92 ms 19484 KB Output is correct
4 Correct 133 ms 23196 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1032 ms 37032 KB Output is correct
2 Incorrect 798 ms 25420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1045 ms 35716 KB Output is correct
2 Incorrect 744 ms 25404 KB Output isn't correct
3 Halted 0 ms 0 KB -