oj.uz

Submission #737613

# Submission time Handle Problem Language Result Execution time Memory
737613 2023-05-07T12:30:47 Z Trent Election (BOI18_election) C++14
100 / 100
 1337 ms 75360 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;

inline node comb(const node& a, const 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){
    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(){
    boost();
    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:77:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         for(auto [r, i] : qu[l]){
      |                  ^
election.cpp:78:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |             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 14 ms 24020 KB Output is correct
2 Correct 15 ms 23892 KB Output is correct
3 Correct 17 ms 24020 KB Output is correct
4 Correct 15 ms 23892 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 15 ms 23892 KB Output is correct
3 Correct 17 ms 24020 KB Output is correct
4 Correct 15 ms 23892 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct
6 Correct 151 ms 34492 KB Output is correct
7 Correct 140 ms 34404 KB Output is correct
8 Correct 139 ms 34264 KB Output is correct
9 Correct 129 ms 34344 KB Output is correct
10 Correct 154 ms 34304 KB Output is correct
11 Correct 137 ms 34568 KB Output is correct
12 Correct 141 ms 34560 KB Output is correct
13 Correct 153 ms 34576 KB Output is correct
14 Correct 148 ms 34612 KB Output is correct
15 Correct 140 ms 34568 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 15 ms 23892 KB Output is correct
3 Correct 17 ms 24020 KB Output is correct
4 Correct 15 ms 23892 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct
6 Correct 151 ms 34492 KB Output is correct
7 Correct 140 ms 34404 KB Output is correct
8 Correct 139 ms 34264 KB Output is correct
9 Correct 129 ms 34344 KB Output is correct
10 Correct 154 ms 34304 KB Output is correct
11 Correct 137 ms 34568 KB Output is correct
12 Correct 141 ms 34560 KB Output is correct
13 Correct 153 ms 34576 KB Output is correct
14 Correct 148 ms 34612 KB Output is correct
15 Correct 140 ms 34568 KB Output is correct
16 Correct 1230 ms 74360 KB Output is correct
17 Correct 1129 ms 73952 KB Output is correct
18 Correct 1236 ms 72680 KB Output is correct
19 Correct 1014 ms 73688 KB Output is correct
20 Correct 1241 ms 73380 KB Output is correct
21 Correct 1200 ms 75172 KB Output is correct
22 Correct 1157 ms 75052 KB Output is correct
23 Correct 1195 ms 75360 KB Output is correct
24 Correct 1337 ms 74944 KB Output is correct
25 Correct 1200 ms 74524 KB Output is correct