Submission #347740

#	Time	Username	Problem	Language	Result	Execution time	Memory
347740		Lukap	Meteors (POI11_met)	C++14	0 / 100	6082 ms	26456 KiB

met

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3 * 1e5 + 7;
const int OFF = (1<<19);

int n,m,k;
int pripadnost[MAXN],zadvoljstvo[MAXN];
int l[MAXN],r[MAXN],xi[MAXN];
vector<int> sektori[MAXN];
long long zbroj[MAXN];

long long tour[2 * OFF];
long long middle[MAXN];
int rijeseno[MAXN];
bool provjeri = false;

long long update(int x){
    x += OFF;
    long long ans = tour[x];
    x/=2;
    while(x>0){
        ans += tour[x];
        x/=2;
    }
    return ans;
}

void query(int a, int b,int v, int x = 1, int lo = 0, int hi = OFF){
//    cout << a << ' ' << b << ' ' << v << ' ' << x << ' ' <<lo << ' ' << hi << "\n";
    if(b<=lo||hi<=a){
        return;
    }
    if(lo>=a&&hi<=b){
        tour[x] += v;
        return;
    }
    int mid = (lo+hi)/2;
    query(a,b,v,x*2,lo,mid);
    query(a,b,v,x*2+1,mid,hi);
}

void bs(int lo, int hi, vector<int> stations) {
//    cout << lo << ' ' << hi << "\n";
    if(hi <= lo + 1 && provjeri == false) {
        for(int i = 0; i < stations.size(); i++) {
            if(middle[stations[i]] == -2) {
                middle[stations[i]]++;
                continue;
            }
            middle[stations[i]] = lo;
        }

        return;

    }

//    cout << lo << ' ' << hi << "\n";

    int mid = (lo + hi) / 2;

    for (int i = 0; i < mid; i++) {
        if(l[i] <= r[i]) query(l[i] - 1,r[i],xi[i]);

        else {
            query(l[i] - 1,m,xi[i]);
            query(0,r[i],xi[i]);
        }
    }

//    for (int i = 0; i < m; i++) cout << update(i) << ' ';
//    cout << "\n";

    vector<int> lijevo,desno;

    for (int i = 0; i < stations.size(); i++) {
        zbroj[stations[i]] = 0;
        for (int j = 0; j < sektori[stations[i]].size(); j++) {
            zbroj[stations[i]] += update(sektori[stations[i]][j]);
            if(zbroj[stations[i]] > zadvoljstvo[stations[i]]) break;
        }

        if(zbroj[stations[i]] < zadvoljstvo[stations[i]]) desno.push_back(stations[i]);

        else lijevo.push_back(stations[i]);

        if(provjeri) continue;

        if(zbroj[stations[i]] == zadvoljstvo[stations[i]]) middle[stations[i]] = mid;

        if(zbroj[stations[i]] < zadvoljstvo[stations[i]] && mid >= k) middle[stations[i]]= -2;
    }


//    cout << mid << "\n";


//    for (int i = 0; i < stations.size(); i++) cout << zbroj[i] << ' ';
//    cout << "\n";

    if(provjeri == true) {
        for (int i = 0; i < desno.size(); i++) middle[desno[i]] = -1;
        return;
    }

    bs(mid + 1, hi, desno);

    for (int i = 0; i < mid; i++) {
        if(l[i] <= r[i]) query(l[i] - 1,r[i],(-1) * xi[i]);

        else {
            query(l[i] - 1,m,(-1) * xi[i]);
            query(0,r[i],(-1) * xi[i]);
        }
    }

    bs(lo, mid, lijevo);

}

int main() {
    memset(middle,-1,sizeof(middle));
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) cin >> pripadnost[i];

    for (int i = 0; i < m; i++) sektori[pripadnost[i] - 1].push_back(i);


    for (int i  = 0; i < n; i++) cin >> zadvoljstvo[i];

    cin >> k;

    for (int i = 0; i < k; i++) cin >> l[i] >> r[i] >> xi[i];

    vector<int> stanice;

    for (int i = 0; i < n; i++) stanice.push_back(i);

    bs(1,k + 1,stanice);

    memset(tour,0,sizeof(tour));

    provjeri = true;
    bs(k, k + 1,stanice);

    for (int i = 0; i < n; i++) {
        if(middle[i] == -1) cout << "NIE" << "\n";

        else cout << middle[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

met.cpp: In function 'void bs(int, int, std::vector<int>)':
met.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i = 0; i < stations.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
met.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < stations.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
met.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int j = 0; j < sektori[stations[i]].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for (int i = 0; i < desno.size(); i++) middle[desno[i]] = -1;
      |                         ~~^~~~~~~~~~~~~~

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