Submission #347772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
347772	2021-01-13T11:29:13 Z	Uncreative	Meteors (POI11_met)	C++14	74 / 100	1494 ms	38116 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];
                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: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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	19180 KB	Output is correct
2	Correct	16 ms	19308 KB	Output is correct
3	Correct	16 ms	19180 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	19180 KB	Output is correct
2	Correct	17 ms	19180 KB	Output is correct
3	Correct	18 ms	19308 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	121 ms	20716 KB	Output is correct
2	Correct	230 ms	23144 KB	Output is correct
3	Correct	171 ms	22508 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	191 ms	21868 KB	Output is correct
2	Correct	191 ms	21868 KB	Output is correct
3	Correct	240 ms	23144 KB	Output is correct
4	Correct	61 ms	21356 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	21356 KB	Output is correct
2	Correct	237 ms	23784 KB	Output is correct
3	Correct	205 ms	19948 KB	Output is correct
4	Correct	172 ms	22908 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	20076 KB	Output is correct
2	Correct	211 ms	21868 KB	Output is correct
3	Correct	136 ms	20460 KB	Output is correct
4	Correct	232 ms	24424 KB	Output is correct

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1494 ms	38116 KB	Output is correct
2	Incorrect	1180 ms	24184 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1477 ms	36864 KB	Output is correct
2	Incorrect	843 ms	24180 KB	Output isn't correct
3	Halted	0 ms	0 KB	-