Submission #1151940

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1151940	2025-02-17 12:11:29	Hamed_Ghaffari	Election (BOI18_election)	C++20	100 / 100	908 ms	201372 KiB

election

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
#define pb push_back
#define SZ(x) int(x.size())
#define maxs(a,b) (a=max(a,b))
#define all(x) x.begin(), x.end()
const int MXN = 5e5+5;
int n, q, ps[MXN];
string s;
vector<int> add[MXN<<2], mx[MXN<<2];
void build(int l=1, int r=n+1, int id=1) {
    mx[id].pb(ps[l]-ps[l-1]);
    for(int i=l+1; i<r; i++) mx[id].pb(max(mx[id].back(), ps[i]-ps[l-1]));
    for(int i=l; i<r; i++)
        if(ps[i]-ps[l-1]==-SZ(add[id])-1)
            add[id].pb(i);
    vector<int> tmp;
    for(int i=SZ(add[id])-1; i>=0; i--) {
        tmp.pb(-1e9);
        if(SZ(tmp)>1) tmp.back() = tmp[SZ(tmp)-2]+1;
        for(int j=add[id][i]; j<(SZ(tmp)>1 ? add[id][i+1] : r); j++)
            maxs(tmp.back(), ps[j]-ps[l-1]+1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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