제출 #347689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347689		Lukap	새로운 문제 (POI11_met)	C++14	0 / 100	6067 ms	31264 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],lazy[2 * OFF];
long long middle[MAXN];
int rijeseno[MAXN];
bool provjeri = false;

void prop(int x, long long lo, long long hi){
    if(lazy[x]==0) return;

    tour[x] += lazy[x]*(hi-lo);
    if(x<OFF){
        lazy[2*x] += lazy[x];
        lazy[2*x+1] += lazy[x];
    }
    lazy[x] = 0;
}

void update(int a, int b, int v, int x = 1, int lo = 0, int hi = OFF){
    prop(x,lo,hi);
    if(b<=lo||hi<=a) return;
    if(lo>=a&&hi<=b){
        lazy[x] = v;
        prop(x,lo,hi);
        return;
    }

    int mid = (lo+hi)/2;
    update(a,b,v,2*x,lo,mid);
    update(a,b,v,2*x+1,mid,hi);

    tour[x] = tour[2*x]+tour[2*x+1];
}

long long query(int a, int b, int x = 1, int lo = 0, int hi = OFF){
//    cout << a  << ' ' << b << ' ' << x << ' ' << lo << ' ' << hi << "\n";

    if(b<=lo||hi<=a) return 0;

    prop(x,lo,hi);

    if(lo>=a&&hi<=b) return tour[x];

    int mid = (lo+hi)/2;

    return query(a,b,2*x,lo,mid)+query(a,b,2*x+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]) update(l[i] - 1,r[i],xi[i]);

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


    for (int i = 0; i < stations.size(); i++) zbroj[stations[i]] = 0;

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

    vector<int> lijevo,desno;

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

    for (int i = 0; i < stations.size(); i++) {
        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;

    }

//    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]) update(l[i] - 1,r[i],(-1) * xi[i]);

        else {
            update(l[i] - 1,m,(-1) * xi[i]);
            update(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));
    memset(lazy,0,sizeof(lazy));

    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;
}

컴파일 시 표준 에러 (stderr) 메시지

met.cpp: In function 'void bs(int, int, std::vector<int>)':
met.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i = 0; i < stations.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
met.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < stations.size(); i++) zbroj[stations[i]] = 0;
      |                     ~~^~~~~~~~~~~~~~~~~
met.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < stations.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
met.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j = 0; j < sektori[stations[i]].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 0; i < stations.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
met.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         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