oj.uz

Submission #737610

# Submission time Handle Problem Language Result Execution time Memory
737610 2023-05-07T12:28:51 Z Trent Election (BOI18_election) C++14
82 / 100
 411 ms 60160 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 = 5e5 + 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 9 ms 12244 KB Output is correct
2 Correct 12 ms 12224 KB Output is correct
3 Correct 9 ms 12244 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 9 ms 12184 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 12 ms 12224 KB Output is correct
3 Correct 9 ms 12244 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 9 ms 12184 KB Output is correct
6 Correct 150 ms 22640 KB Output is correct
7 Correct 150 ms 23500 KB Output is correct
8 Correct 155 ms 23312 KB Output is correct
9 Correct 153 ms 23504 KB Output is correct
10 Correct 149 ms 23516 KB Output is correct
11 Correct 154 ms 23628 KB Output is correct
12 Correct 148 ms 23724 KB Output is correct
13 Correct 157 ms 23816 KB Output is correct
14 Correct 158 ms 23704 KB Output is correct
15 Correct 152 ms 23672 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 12 ms 12224 KB Output is correct
3 Correct 9 ms 12244 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 9 ms 12184 KB Output is correct
6 Correct 150 ms 22640 KB Output is correct
7 Correct 150 ms 23500 KB Output is correct
8 Correct 155 ms 23312 KB Output is correct
9 Correct 153 ms 23504 KB Output is correct
10 Correct 149 ms 23516 KB Output is correct
11 Correct 154 ms 23628 KB Output is correct
12 Correct 148 ms 23724 KB Output is correct
13 Correct 157 ms 23816 KB Output is correct
14 Correct 158 ms 23704 KB Output is correct
15 Correct 152 ms 23672 KB Output is correct
16 Runtime error 411 ms 60160 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -