oj.uz

Submission #469683

# Submission time Handle Problem Language Result Execution time Memory
469683 2021-09-01T15:19:02 Z MohamedFaresNebili Election (BOI18_election) C++14
28 / 100
 3000 ms 1528 KB 
#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;

#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

const ll MOD = 998244353;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const int nx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
const int ny[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

ll n, q, arr[500005];

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    string s; cin>>n>>s>>q;
    while(q--) {
        ll a, b; cin>>a>>b; a--; b--;
        ll cap=0, tony=0; int vis[n];
        memset(vis, 0, sizeof vis);
        for(int i=a;i<=b;i++) {
            if(s[i]=='C') cap++;
            if(s[i]=='T') {
                tony++;
                if(tony>cap) {
                    vis[i]=1; tony--;
                }
            }
        }
        cap=0, tony=0; ll ans=0;
        for(int i=b;i>=a;i--) {
            if(s[i]=='C') cap++;
            if(s[i]=='T'&&!vis[i]) {
                tony++;
                if(tony>cap) {
                    vis[i]=1; tony--;
                }
            }
        }
        for(int i=a;i<=b;i++)
            if(vis[i]) ans++;
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 9 ms 336 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 8 ms 352 KB Output is correct
5 Correct 5 ms 332 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 9 ms 336 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 8 ms 352 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Execution timed out 3067 ms 1528 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 9 ms 336 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 8 ms 352 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Execution timed out 3067 ms 1528 KB Time limit exceeded
7 Halted 0 ms 0 KB -