oj.uz

Submission #315776

# Submission time Handle Problem Language Result Execution time Memory
315776 2020-10-24T00:53:49 Z i_am_noob Election (BOI18_election) C++17
100 / 100
 801 ms 40288 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
//#define inf 2000000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=500005;
//i_am_noob
int n,a[maxn],q,l,r;
string str;

struct noob{
    int minn,maxx,diffmax;
    noob(){}
    noob(int i, int j, int k):minn(i),maxx(j),diffmax(k){}
};
noob val[maxn*4],def(inf,-inf,-inf);

noob Merge(noob i, noob j){return noob(min(i.minn,j.minn),max(i.maxx,j.maxx),max(max(i.diffmax,j.diffmax),j.maxx-i.minn));}

void build(int k, int l, int r){
    if(l==r){
        val[k]=noob(a[l-1],a[l-1],0);
        return;
    }
    build(k<<1,l,l+r>>1),build(k<<1|1,(l+r>>1)+1,r);
    val[k]=Merge(val[k<<1],val[k<<1|1]);
}

noob query(int k, int l, int r, int ql, int qr){
    if(l>qr||r<ql) return def;
    if(ql<=l&&qr>=r) return val[k];
    return Merge(query(k<<1,l,l+r>>1,ql,qr),query(k<<1|1,(l+r>>1)+1,r,ql,qr));
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> str;
    a[0]=0;
    rep(n) a[i+1]=a[i]+(str[i]=='C'?1:-1);
    build(1,1,n+1);
    cin >> q;
    while(q--){
        cin >> l >> r;
        noob x=query(1,1,n+1,l,r+1);
        print1(a[l-1]-x.minn+x.diffmax-(a[r]-x.minn));
    }
    return 0;
}

Compilation message

election.cpp: In function 'void build(long long int, long long int, long long int)':
election.cpp:53:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     build(k<<1,l,l+r>>1),build(k<<1|1,(l+r>>1)+1,r);
      |                  ~^~
election.cpp:53:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     build(k<<1,l,l+r>>1),build(k<<1|1,(l+r>>1)+1,r);
      |                                        ~^~
election.cpp: In function 'noob query(long long int, long long int, long long int, long long int, long long int)':
election.cpp:60:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     return Merge(query(k<<1,l,l+r>>1,ql,qr),query(k<<1|1,(l+r>>1)+1,r,ql,qr));
      |                               ~^~
election.cpp:60:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     return Merge(query(k<<1,l,l+r>>1,ql,qr),query(k<<1|1,(l+r>>1)+1,r,ql,qr));
      |                                                           ~^~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 74 ms 8440 KB Output is correct
7 Correct 65 ms 8564 KB Output is correct
8 Correct 69 ms 8568 KB Output is correct
9 Correct 63 ms 8440 KB Output is correct
10 Correct 75 ms 8312 KB Output is correct
11 Correct 77 ms 8568 KB Output is correct
12 Correct 74 ms 8568 KB Output is correct
13 Correct 77 ms 8568 KB Output is correct
14 Correct 74 ms 8568 KB Output is correct
15 Correct 78 ms 8520 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 74 ms 8440 KB Output is correct
7 Correct 65 ms 8564 KB Output is correct
8 Correct 69 ms 8568 KB Output is correct
9 Correct 63 ms 8440 KB Output is correct
10 Correct 75 ms 8312 KB Output is correct
11 Correct 77 ms 8568 KB Output is correct
12 Correct 74 ms 8568 KB Output is correct
13 Correct 77 ms 8568 KB Output is correct
14 Correct 74 ms 8568 KB Output is correct
15 Correct 78 ms 8520 KB Output is correct
16 Correct 801 ms 39268 KB Output is correct
17 Correct 638 ms 38796 KB Output is correct
18 Correct 707 ms 39176 KB Output is correct
19 Correct 595 ms 38540 KB Output is correct
20 Correct 784 ms 38412 KB Output is correct
21 Correct 779 ms 40080 KB Output is correct
22 Correct 766 ms 40196 KB Output is correct
23 Correct 759 ms 40288 KB Output is correct
24 Correct 761 ms 39820 KB Output is correct
25 Correct 788 ms 39460 KB Output is correct