Submission #707481

#	Time	Username	Problem	Language	Result	Execution time	Memory
707481		MinhAnhnd	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	212 KiB

segments

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define Nmax 500001
long long N,Q,A[Nmax],S[Nmax] ={};

bool ss(tuple<long long,long long,long long> a,tuple<long long,long long,long long> b){
    return get<0>(a) < get<0>(b);
}

bool operator<(pair<long long,long long> a , pair<long long,long long> b){
    if(a.first == b.first) return a.second<b.second;
    return a.first<b.first;
}
int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	set<pair<long long,long long>> then;
    set<pair<long long,long long>> now;
    set<pair<long long,long long>> past;
    long long then_val = -1;
    long long now_val = 0;
    now.insert(make_pair(0,0));

	cin>>N;
    for (long long i = 1;i<=N;i++){
        cin>>A[i];
        S[i] = S[i-1]+A[i];
        //first element to be greater than value;
        long long bound = S[i];
        auto pointer = now.upper_bound(make_pair(S[i],1000000000000000001));
        if(pointer==now.begin()){
            auto new_pointer = then.upper_bound(make_pair(S[i],1000000000000000001));
            new_pointer--;
            long long delta = S[i]-new_pointer->second;
            auto checker = now.upper_bound(make_pair(S[i]+delta,S[i]));
            if(checker!=now.begin()){
                checker--;
                auto comp = checker;
                checker++;
                if(comp->second>checker->second) continue;
            }

            auto it = now.insert(make_pair(S[i]+delta,S[i])).first;
            while(it!=prev(now.end())){
                auto checker = next(it);
                if (it->second > checker->second){
                    now.erase(checker);
                } else continue;
            }
            /*if(!past.empty()){
            new_pointer = past.upper_bound(make_pair(S[i],1000000000000000001));
            new_pointer--;
            delta = S[i]-new_pointer->second;
            then.insert(make_pair(S[i]+delta,S[i]));}*/

        } else{

            then_val++;
            now_val++;

            pointer--;
            long long delta = S[i]-pointer->second;
            swap(past,then);
            swap(then,now);
            now.clear();
            //cout<<S[i]+delta<<" "<<S[i]<<" "<<pointer->second<<" "<<endl;
            now.insert(make_pair(S[i]+delta,S[i]));

            /*auto new_pointer = then.upper_bound(make_pair(S[i],1000000000000000001));
            new_pointer--;
             delta = S[i]-new_pointer->second;
            now.insert(make_pair(S[i]+delta,S[i]));

            if(!past.empty()){
            new_pointer = past.upper_bound(make_pair(S[i],1000000000000000001));
            new_pointer--;
            delta = S[i]-new_pointer->second;
            then.insert(make_pair(S[i]+delta,S[i]));}*/
        }
    }
    cout<<now_val;

}
/*
int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);

    string s;
    long long l[Nmax];
    long long r[Nmax];
    long long fi[Nmax] ={};
    long long specialloc[Nmax] ={};
    long long startspecial[3][Nmax] = {};
    long long endspecial[3][Nmax] = {};
    long long comlen = 1;

    cin>>N>>Q;
    cin>>s;
    string com;
    com += s[0];
    fi[1] = 0;
    for(long long i = 1;i<=N-1;i++){
        if(s[i]!=s[i-1]) {comlen++; com += s[i];}
        fi[i+1] = comlen - 1;
    }

    for(long long i = 1;i<=Q;i++){
        cin>>l[i]>>r[i];
        l[i] = fi[l[i]];
        r[i] = fi[r[i]];

        long long ans = 0;
        long long delta = r[i]- l[i]+1;
        if(com[l[i]]==com[r[i]]) delta--;
        while(delta>=4){
            delta -=2;
            ans++;
        }
        ans += delta - 1;
        cout<<max(ans,(long long)0)<<endl;
    }
}


    //com += '0';
    /*vector<tuple<long long,long long,long long>> special;
    for(char i = 'A';i<='C';i++){
        long long lastfound = -1;
        for (long long j = 0;j<=comlen;j++){
            if (j==comlen) com[j]=i;
            if(com[j]==i){
                if((j-lastfound)>3){
                    //cout<<j<<" "<<lastfound<<endl;
                    special.push_back(make_tuple((long long)lastfound+1,(long long)j-1,(long long)(i-'A')));
                    specialloc[lastfound+1]++;
                    specialloc[j-1]--;
                }
                lastfound = j;
            }
        }
    }
    sort(special.begin(),special.end(),ss);
    for (auto i: special){
        long long a,b,c;
        tie(a,b,c) = i;
        long long need_to_end_at_or_after = a + 2;
        long long need_to_start_at_or_before = b - 2;
        if(specialloc[a]==0){
            endspecial[(long long)(i-'A')][a-1];
        } else{

        }
        if(specialloc[b]==0){

        } else{

        }

    }
    //cout<<com<<endl;
*/

Compilation message (stderr)

segments.cpp:131:5: warning: "/*" within comment [-Wcomment]
  131 |     /*vector<tuple<long long,long long,long long>> special;
      |      
segments.cpp: In function 'int main()':
segments.cpp:33:19: warning: unused variable 'bound' [-Wunused-variable]
   33 |         long long bound = S[i];
      |                   ^~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27