oj.uz

Submission #557385

# Submission time Handle Problem Language Result Execution time Memory
557385 2022-05-05T09:02:47 Z new_acc Ekoeko (COCI21_ekoeko) C++14
20 / 110
 37 ms 27208 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg[(SS<<1)+10],wsk[N],il[N],pom[N];
vi g[N];
void upd(int a,int b){
    for(a+=SS;a>0;a>>=1) seg[a]+=b;
}
int Query(int a,int b){
    int res=0;
    for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
        if(!(a&1)) res+=seg[a+1];
        if(b&1) res+=seg[b-1];
    }
    return res;
}
int cnt(string a,string b){
    a="#"+a,b="#"+b;
    for(int i=1;i<a.size();i++){
        int curr=int(a[i])-96;
        g[curr].push_back(i);
    }
    int res=0;
    for(int i=1;i<b.size();i++){
        int curr=int(b[i])-96;
        int currl=g[curr][wsk[curr]++];
        res+=Query(currl,a.size());
        upd(currl,1);
    }
    return res;
}
void solve(){   
    int n;
    string s; 
    cin>>n>>s;
    for(int i=0;i<s.size();i++) il[int(s[i])-96]++;
    string res;
    for(int i=0;i<s.size();i++){
        pom[int(s[i])-96]++;
        if(pom[int(s[i])-96]<=(il[int(s[i])-96]>>1)) res+=s[i];
    }
    res=res+res;
    cout<<cnt(s,res)<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message

Main.cpp: In function 'int cnt(std::string, std::string)':
Main.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=1;i<a.size();i++){
      |                 ~^~~~~~~~~
Main.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=1;i<b.size();i++){
      |                 ~^~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<s.size();i++) il[int(s[i])-96]++;
      |                 ~^~~~~~~~~
Main.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 20 ms 25224 KB Output is correct
3 Correct 28 ms 26188 KB Output is correct
4 Incorrect 37 ms 27208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 20 ms 25224 KB Output is correct
3 Correct 28 ms 26188 KB Output is correct
4 Incorrect 37 ms 27208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 20 ms 25224 KB Output is correct
3 Correct 28 ms 26188 KB Output is correct
4 Incorrect 37 ms 27208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 13 ms 23812 KB Output is correct
4 Correct 14 ms 23852 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 17 ms 23892 KB Output is correct
8 Correct 14 ms 23892 KB Output is correct
9 Correct 14 ms 23892 KB Output is correct
10 Correct 13 ms 23908 KB Output is correct
11 Correct 15 ms 23808 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 20 ms 25224 KB Output is correct
3 Correct 28 ms 26188 KB Output is correct
4 Incorrect 37 ms 27208 KB Output isn't correct
5 Halted 0 ms 0 KB -