Submission #1012470

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1012470	2024-07-02T08:19:56 Z	Almonther	Difference (POI11_roz)	C++	100 / 100	526 ms	26596 KB

#include<bits/stdc++.h>

#define ll long long
#define co cout<<
#define suiii ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
// stuff
ll n;
string s;
ll mx=0;
vector<ll>v[27];
ll pref[1000001],arr[1000001];
void solve(){
    cin>>n>>s;
    for(int i=0;i<n;i++) v[s[i]-'a'].push_back(i);
    for(int i=0;i<26;i++){
        if(v[i].size()==0) continue;
        for(int j=0;j<26;j++){
            if(v[j].size()==0) continue;
            ll l,r;
            l=r=0;
            while(l!=v[i].size()||r!=v[j].size()){
                if(l==v[i].size()){
                    r++;
                    arr[l+r]=-1;
                }
                else if(r==v[j].size()){
                    l++;
                    arr[l+r]=1;
                }
                else if(v[i][l]<v[j][r]){
                    l++;
                    arr[l+r]=1;
                }
                else{
                    r++;
                    arr[l+r]=-1;
                }
            }
            ll mn=1e18;
            pref[0]=0;
            for(int k=1;k<=l+r;k++) pref[k]=pref[k-1]+arr[k];
            ll last=0;
            for(int k=1;k<=l+r;k++){
                if(arr[k]==-1){
                    for(int r=last;r<k;r++) mn=min(mn,pref[r]);
                    mn=min(mn,0ll);
                    last=k;
                }
                mx=max(mx,pref[k]-mn);
            }
        }
    }
    co mx;
}

int main(){
    suiii
    int tt=1;
    // cin>>tt;
    while(tt--){
        solve();
    }
}

Compilation message

roz.cpp: In function 'void solve()':
roz.cpp:22:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             while(l!=v[i].size()||r!=v[j].size()){
      |                   ~^~~~~~~~~~~~~
roz.cpp:22:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             while(l!=v[i].size()||r!=v[j].size()){
      |                                   ~^~~~~~~~~~~~~
roz.cpp:23:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |                 if(l==v[i].size()){
      |                    ~^~~~~~~~~~~~~
roz.cpp:27:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |                 else if(r==v[j].size()){
      |                         ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	604 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	1628 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	483 ms	15352 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	255 ms	11592 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	526 ms	15396 KB	Output is correct
2	Correct	422 ms	13812 KB	Output is correct
3	Correct	73 ms	11164 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	460 ms	15216 KB	Output is correct
2	Correct	66 ms	20816 KB	Output is correct
3	Correct	62 ms	13864 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	509 ms	15344 KB	Output is correct
2	Correct	43 ms	26596 KB	Output is correct
3	Correct	155 ms	12648 KB	Output is correct