oj.uz

Submission #737612

# Submission time Handle Problem Language Result Execution time Memory
737612 2023-05-07T12:29:37 Z Trent Election (BOI18_election) C++14
100 / 100
 1362 ms 83092 KB 
#include "bits/stdc++.h"
 
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}

const int MN = 1e6 + 10, ME = 4 * MN, INF = 1e7;

struct node{
    int mi, ma, mad, lz;
} seg[ME];
int n;

node comb(node a, node b){
    assert(a.lz == 0 && b.lz == 0);
    return {min(a.mi, b.mi), max(a.ma, b.ma), max({a.ma, b.ma, a.mad, b.mad, b.ma - a.mi}), 0};
}
void down(int v){
    if(2*v+1 < ME){
        seg[2*v].mi += seg[v].lz;
        seg[2*v].ma += seg[v].lz;
        seg[2*v].lz += seg[v].lz;
        seg[2*v+1].mi += seg[v].lz;
        seg[2*v+1].ma += seg[v].lz;
        seg[2*v+1].lz += seg[v].lz;
        seg[v].lz = 0;
    }
}
void upd(int l, int r, int by, int v=1, int nl=1, int nr=n){
    down(v);
    if(l > r) return;
    else if(nl == l && nr == r){
        seg[v].mi += by;
        seg[v].ma += by;
        seg[v].lz += by;
        down(v);
    } else {
        int mid = (nl+nr) / 2;
        upd(l, min(mid, r), by, 2*v, nl, mid);
        upd(max(mid+1, l), r, by, 2*v+1, mid+1, nr);
        seg[v] = comb(seg[2*v], seg[2*v+1]);
    }
}
node qry(int l, int r, int v=1, int nl=1, int nr=n){
    down(v);
    if(l > r) return {INF, -INF, 0, 0};
    else if(nl == l && nr == r) return seg[v];
    else {
        int mid = (nl+nr)/2;
        return comb(
            qry(l, min(mid, r), 2*v, nl, mid),
            qry(max(mid+1, l), r, 2*v+1, mid+1, nr)
        );
    }
}

int ans[MN]; vector<pii> qu[MN];
signed main(){
    cin >> n;
    string s; cin >> s;
    int q; cin >> q;
    forR(i, q){
        int l, r; cin >> l >> r;
        qu[l].push_back({r, i});
    }
    for(int l = n; l >= 1; --l){
        int ch = s[l-1] == 'C' ? 1 : -1;
        upd(l, n, ch);
        for(auto [r, i] : qu[l]){
            auto [mi, ma, mad, lz] = comb({0, 0, 0, 0}, qry(l, r));
            int ct = -mi;
            int la = mad;
            int las = qry(r, r).mi - mi;
            ans[i] = ct + la - las;
        }
    }
    forR(i, q) cout << ans[i] << '\n';
}

Compilation message

election.cpp: In function 'bool operator<(pii, pii)':
election.cpp:14:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                    ~~~~~~~~~~~^~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:78:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |         for(auto [r, i] : qu[l]){
      |                  ^
election.cpp:79:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |             auto [mi, ma, mad, lz] = comb({0, 0, 0, 0}, qry(l, r));
      |                  ^

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23892 KB Output is correct
2 Correct 19 ms 23916 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 16 ms 23908 KB Output is correct
5 Correct 15 ms 23892 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23892 KB Output is correct
2 Correct 19 ms 23916 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 16 ms 23908 KB Output is correct
5 Correct 15 ms 23892 KB Output is correct
6 Correct 165 ms 34484 KB Output is correct
7 Correct 153 ms 34360 KB Output is correct
8 Correct 156 ms 34180 KB Output is correct
9 Correct 146 ms 34348 KB Output is correct
10 Correct 158 ms 34232 KB Output is correct
11 Correct 158 ms 34532 KB Output is correct
12 Correct 190 ms 34464 KB Output is correct
13 Correct 168 ms 34448 KB Output is correct
14 Correct 154 ms 34476 KB Output is correct
15 Correct 160 ms 34484 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23892 KB Output is correct
2 Correct 19 ms 23916 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 16 ms 23908 KB Output is correct
5 Correct 15 ms 23892 KB Output is correct
6 Correct 165 ms 34484 KB Output is correct
7 Correct 153 ms 34360 KB Output is correct
8 Correct 156 ms 34180 KB Output is correct
9 Correct 146 ms 34348 KB Output is correct
10 Correct 158 ms 34232 KB Output is correct
11 Correct 158 ms 34532 KB Output is correct
12 Correct 190 ms 34464 KB Output is correct
13 Correct 168 ms 34448 KB Output is correct
14 Correct 154 ms 34476 KB Output is correct
15 Correct 160 ms 34484 KB Output is correct
16 Correct 1343 ms 74480 KB Output is correct
17 Correct 1189 ms 81264 KB Output is correct
18 Correct 1291 ms 80204 KB Output is correct
19 Correct 1171 ms 81268 KB Output is correct
20 Correct 1347 ms 81256 KB Output is correct
21 Correct 1358 ms 82948 KB Output is correct
22 Correct 1344 ms 82936 KB Output is correct
23 Correct 1352 ms 83092 KB Output is correct
24 Correct 1362 ms 82760 KB Output is correct
25 Correct 1359 ms 82176 KB Output is correct