oj.uz

Submission #978849

# Submission time Handle Problem Language Result Execution time Memory
978849 2024-05-09T19:28:16 Z rakhim_ova Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 70120 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Incorrect 1 ms 428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Incorrect 1 ms 428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Execution timed out 2089 ms 64448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 70120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Incorrect 1 ms 428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Incorrect 1 ms 428 KB Output isn't correct
3 Halted 0 ms 0 KB -