Submission #1144285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144285		bestbest	Pilot (NOI19_pilot)	C++20	63 / 100	1097 ms	43588 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define  en '\n'
#define  sp ' '
typedef long long ll;
#define Linux ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int,int>

const int N=1e6+10;

vector<int> v[N];
int n,Q,temp,t;
ll ans[N];
ll qs[N];
set<pii> s;
bool chk;

int main(){Linux
    cin >> n >> Q;

    for(int i=1;i<N;i++)qs[i]=qs[i-1]+i;
    
    for(int i=1;i<=n;i++){
        cin >> temp;
        v[temp].push_back(i);
    }
    // cout << "bef" << endl;
    for(int i=1;i<N;i++){
        if(v[i].size()==0)continue;
        // cout << "seg" << i << endl;
        for(int j:v[i]){
            s.insert({j,j});
        }
        

        // for(auto [a,b]:s){
        //     cout << a << ',' << b << sp;
        // }
        // cout << endl;

        int cnt=1;
        // cout << "size" << s.size() << endl;
        for(auto it=s.begin();it!=s.end();it++){
            if(chk){
                it--;
                chk=0;
            }
            // cout << "cnt" << cnt << endl;
            // cout << "it" << it->first << sp << it->second << endl;
            auto it2=++it;
            it--;
            pii pa={it->first,it->second},pb={it2->first,it2->second};
            // cout << "diff " << (it2->first)-(it->second) << endl;
            if((it2->first)-(it->second)==1){
                s.insert({pa.first,pb.second});
                s.erase(pa);
                s.erase(pb);
                it=s.lower_bound({pa.first,pb.second});
                // cout << "newbef" << (it->first) << sp << (it->second) << endl;
                chk=1;
                if(it!=s.begin()){
                    it--;
                    // cout << "minus" << endl;
                }
                // cout << "new" << (it->first) << sp << (it->second) << endl;
                // cout << "erase" << sp;
                // for(auto [a,b]:s)cout << a << ',' << b << sp;
                // cout << endl;
            }
            // cout << "exitcnt" << cnt++ << endl;
            // cout << "endlll" << endl;
        }


        // for(auto [a,b]:s){
        //     cout << a << ',' << b << sp;
        // }
        // cout << endl;

        for(auto [a,b]:s){
            ans[i]+=qs[b-a+1];
        }
        //cout << "seggf" << endl;

    }
    for(int i=1;i<=N;i++){
        if(ans[i]==0)ans[i]=ans[i-1];
    }
    while(Q--){
        cin >> t;
        cout << ans[t] << en;
    }
    // for(int i=1;i<=n;i++){
    //     cout << ans[i] << en;
    // }

    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:87:17: warning: iteration 1000009 invokes undefined behavior [-Waggressive-loop-optimizations]
   87 |         if(ans[i]==0)ans[i]=ans[i-1];
      |            ~~~~~^
pilot.cpp:86:18: note: within this loop
   86 |     for(int i=1;i<=N;i++){
      |                 ~^~~

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 0 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11