답안 #347719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347719	2021-01-13T10:41:06 Z	Uncreative	Meteors (POI11_met)	C++14	0 / 100	815 ms	28556 KB

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>

using namespace std;

const int maxn = 300030;

long long loga[maxn];

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

long long query(int x){
    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] = 0;
        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";
        //cout << mn[k].size() << endl;
        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]);
            }
            /*if (i == 3){
                for (int e = 1; e <= 3; e++){
                    long long z = 0;
                    for (int f = 0; f < d[e].size(); f++){
                        z += query(d[e][f]);
                    }
                    cout << "Z " << e << " " <<  z << endl;
                }
            }*/
            //cerr << "555" << endl;
            //cerr << "Mn " << mn[i].size() << endl;
            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 (e == 1 && i == 3){
                    cout << "da" << endl;
                }*/
                if (z >= p[e]){
                    sol[e] = i;
                    hi[e] = i;
                    nmn.push_back(make_pair((lo[i] + hi[i]) / 2, e));
                }
                else {
                    lo[e] = i + 1;
                    //cout << "mid " << (lo[i] + hi[i] / 2) << endl;
                    nmn.push_back(make_pair((lo[i] + hi[i]) / 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:98:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for (int t = 0; t < mn[i].size(); t++){
      |                             ~~^~~~~~~~~~~~~~
met.cpp:103:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                 for (int f = 0; f < d[e].size(); f++){
      |                                 ~~^~~~~~~~~~~~~
met.cpp:125: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]
  125 |         for (int t = 0; t < nmn.size(); t++){
      |                         ~~^~~~~~~~~~~~

Subtask #1
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	14 ms	16876 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	15 ms	16876 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	93 ms	18028 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	131 ms	18284 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	108 ms	18092 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	160 ms	17900 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	807 ms	28556 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	815 ms	27868 KB	Output isn't correct
2	Halted	0 ms	0 KB	-