Submission #347773

#	Time	Username	Problem	Language	Result	Execution time	Memory
347773		Uncreative	Meteors (POI11_met)	C++14	100 / 100	2541 ms	63976 KiB

met

#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 (stderr)

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++){
      |                         ~~^~~~~~~~~~~~

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