답안 #347773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347773 2021-01-13T11:30:08 Z Uncreative Meteors (POI11_met) C++14
100 / 100
2541 ms 63976 KB
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>

using namespace std;

const int maxn = 300030;

unsigned long long loga[2 * maxn];

void update(int x, int val){
    for (; x < 2 * maxn; x += (x & (-x))){
        loga[x] += val;
    }
}

long long query(int x){
    unsigned long long ret = 0;
    for (; x > 0; x -= (x & (-x))){
        ret += loga[x];
    }
    return ret;
}

vector<int> d[maxn];
long long p[maxn];

int l[maxn];
int r[maxn];
int a[maxn];

int lo[maxn];
int hi[maxn];
int mid[maxn];

vector<int> mn[maxn];

vector<pair<int, int > > nmn;

int sol[maxn];

int main(){
    ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x;
        cin >> x;
        d[x].push_back(i);
    }
    for (int i = 1; i <= n; i++){
        cin >> p[i];
    }
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++){
        cin >> l[i] >> r[i] >> a[i];
    }
    for (int i = 1; i <= n; i++){
        lo[i] = 1;
        hi[i] = k;
        mid[i] = (lo[i] + hi[i]) / 2;
        mn[mid[i]].push_back(i);
    }



    //cout << 77 << endl;
    int lg = (int)log2((double)k) + 3;
    //cout << " " << lg << endl;
    for (int j = 0; j < lg; j++){
        //cerr << "j " << j << "\n";
    for (int i = 1; i <= k; i++){
            //cerr << i << "\n";
            if (l[i] <= r[i]){
                update(l[i], a[i]);
                update(r[i] + 1, -a[i]);
            }
            else {
                update(l[i], a[i]);
                update(m + 1, -a[i]);
                update(1, a[i]);
                update(r[i] + 1, -a[i]);
            }
            for (int t = 0; t < mn[i].size(); t++){
                //cerr << "T " << t << endl;
                int e = mn[i][t];
                unsigned long long z = 0;

                for (int f = 0; f < d[e].size(); f++){
                    z += query(d[e][f]);
                }
                if (z >= p[e]){
                    sol[e] = i;
                    hi[e] = i;
                    nmn.push_back(make_pair((lo[e] + hi[e]) / 2, e));
                }
                else {
                    lo[e] = i + 1;
                    //cout << "mid " << (lo[i] + hi[i] / 2) << endl;
                    nmn.push_back(make_pair((lo[e] + hi[e]) / 2, e));
                }
            }
            //cerr << "666" << endl;
            mn[i].clear();

            //cerr << "777" << endl;
        }
        for (int t = 0; t < nmn.size(); t++){
            mn[nmn[t].first].push_back(nmn[t].second);
        }
        nmn.clear();
        memset(loga, 0, sizeof(loga));
    }
    for (int i = 1; i <= n; i++){
        if (sol[i] > 0){
            cout << sol[i] << "\n";
        }
        else {
            cout << "NIE\n";
        }
    }

}

Compilation message

met.cpp: In function 'int main()':
met.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int t = 0; t < mn[i].size(); t++){
      |                             ~~^~~~~~~~~~~~~~
met.cpp:91:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 for (int f = 0; f < d[e].size(); f++){
      |                                 ~~^~~~~~~~~~~~~
met.cpp:94:23: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   94 |                 if (z >= p[e]){
      |                     ~~^~~~~~~
met.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for (int t = 0; t < nmn.size(); t++){
      |                         ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19180 KB Output is correct
2 Correct 16 ms 19180 KB Output is correct
3 Correct 16 ms 19180 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19180 KB Output is correct
2 Correct 16 ms 19180 KB Output is correct
3 Correct 19 ms 19308 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 20716 KB Output is correct
2 Correct 222 ms 23016 KB Output is correct
3 Correct 165 ms 22508 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 21868 KB Output is correct
2 Correct 210 ms 21996 KB Output is correct
3 Correct 231 ms 23144 KB Output is correct
4 Correct 58 ms 21356 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 21152 KB Output is correct
2 Correct 244 ms 23784 KB Output is correct
3 Correct 217 ms 19948 KB Output is correct
4 Correct 179 ms 23016 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 20332 KB Output is correct
2 Correct 220 ms 21868 KB Output is correct
3 Correct 136 ms 20460 KB Output is correct
4 Correct 236 ms 24424 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1498 ms 38372 KB Output is correct
2 Correct 1146 ms 24184 KB Output is correct
3 Correct 1073 ms 22380 KB Output is correct
4 Correct 2401 ms 59660 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1460 ms 36836 KB Output is correct
2 Correct 845 ms 24052 KB Output is correct
3 Correct 841 ms 21612 KB Output is correct
4 Correct 2541 ms 63976 KB Output is correct