제출 #1179356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179356		pcheloveks	Election (BOI18_election)	C++20	28 / 100	3095 ms	764 KiB

election

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset

#define endl '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;

const ll DIM = 700007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 998244353;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;

const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };

FILE* stream;

bool used[DIM];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen_s(&stream, "input.txt", "r", stdin);
    //freopen_s(&stream, "output.txt", "w", stdout);

    ll n, q;
    string s;

    cin >> n;
    cin >> s;
    cin >> q;
    for (int j = 1; j <= q; j++) {
        ll L, R;
        cin >> L >> R;
        
        ll x = 0;
        ll res = 0;
        for (int i = L - 1; i <= R - 1; i++) {
            if (s[i] == 'T') x--;
            else x++;

            if (x < 0) {
                used[i] = true;
                x++;
                res++;
            }
        }
        x = 0;
        for (int i = R - 1; i >= L - 1; i--) {
            if (!used[i]) {
                if (s[i] == 'T') x--;
                else x++;
            }

            if (x < 0) {
                res++;
                used[i] = true;
                x++;
            }
        }
        for (int i = L - 1; i < R; i++) used[i] = false;
        cout << res << endl;
    }

    return 0;
}

• Subtask 1: 28 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18