Submission #978849

#	Time	Username	Problem	Language	Result	Execution time	Memory
978849		rakhim_ova	Sequence (APIO23_sequence)	C++17	0 / 100	2089 ms	70120 KiB

sequence

#include <bits/stdc++.h>
 
using namespace std;

using ll = long long;
 
ll INF=1e13;
 

int sequence(int n, std::vector<int> a) {
    

    vector<vector<int>> ind(n+1);
    for(int i=0; i<n; i++){
        ind[a[i]].push_back(i);
    }
    vector<int> new_a(n);
    int mx=1;
    for(int i=1; i<=n; i++){
        if(i==1){
            for(int j=0; j<n; j++){
                if(a[j]<i) new_a[j]=-1;
                else if(a[j]>i) new_a[j]=1;
                else new_a[j]=-1;
            }
        }
        else{
            for(int j=0; j<ind[i-1].size(); j++){
                new_a[ind[i-1][j]]=-1;
            }
            for(int j=0; j<ind[i].size(); j++){
                new_a[ind[i][j]]=-1;
            }
        }
        map<int, pair<int, int>> mp;
        int sm=0;
        // cout << i << '\n';
        // for(auto x: new_a){
        //     cout << x << ' ';
        // }
        // cout << '\n';
        for(int j=0; j<n; j++){
            sm+=new_a[j];
            // cout << sm << ' ';
            if(mp.find(sm)!=mp.end()){
                mp[sm].second=j;
            }
            else{
                mp[sm].first=j;
                mp[sm].second=j;
            }
        }
        // cout << '\n';
        vector<int> pref(n);
        int cnt=0;
        for(int j=0; j<n; j++){
            if(a[j]==i){
                cnt++;
            }
            pref[j]=cnt;
        }
        
        for(auto x: mp){
            // cout << x.first << ' ' << x.second.first << ' ' << x.second.second << '\n';
            if(x.second.first==0){
                mx=max(mx, pref[x.second.second]);
            }
            else{
                mx=max(mx, pref[x.second.second]-pref[x.second.first-1]);
            }
        }
        
        // for(auto x: pref){
        //     cout << x << ' ';
        // }
        // cout << '\n';
    }
    return mx;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             for(int j=0; j<ind[i-1].size(); j++){
      |                          ~^~~~~~~~~~~~~~~~
sequence.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for(int j=0; j<ind[i].size(); j++){
      |                          ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18