oj.uz

Submission #481194

# Submission time Handle Problem Language Result Execution time Memory
481194 2021-10-19T18:36:46 Z urosk Election (BOI18_election) C++14
100 / 100
 724 ms 39984 KB 
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 500005
ll n,q;
ll a[maxn];
struct node{
    ll l,r,s,ans;
    node operator+(node b){
        node rez;
        rez.l = max(l,s+b.l);
        rez.r = max(b.r,r+b.s);
        rez.s = s + b.s;
        rez.ans = max({l+b.r,ans+b.s,s+b.ans});
        return rez;
    }
};
node t[4*maxn];
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        if(a[tl]==1) t[v] = {1,1,1,1};
        else t[v] = {0,0,-1,0};
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid);
    init(2*v+1,mid+1,tr);
    t[v] = t[2*v]+t[2*v+1];
}
node reshi(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {0,0,0,0};
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return reshi(2*v,tl,mid,l,min(mid,r)) + reshi(2*v+1,mid+1,tr,max(l,mid+1),r);
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n;
    for(ll i = 1;i<=n;i++){
        char c;
        cin >> c;
        if(c=='T') a[i] = 1;
        else a[i] = -1;
    }
    init(1,1,n);
    cin >> q;
    while(q--){
        ll l,r; cin >> l >> r;
        cout<<reshi(1,1,n,l,r).ans<<endl;
    }
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

election.cpp: In function 'void setIO(std::string)':
election.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:33:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 63 ms 9236 KB Output is correct
7 Correct 59 ms 9284 KB Output is correct
8 Correct 73 ms 9228 KB Output is correct
9 Correct 62 ms 9252 KB Output is correct
10 Correct 68 ms 9112 KB Output is correct
11 Correct 63 ms 9356 KB Output is correct
12 Correct 76 ms 9352 KB Output is correct
13 Correct 63 ms 9384 KB Output is correct
14 Correct 67 ms 9316 KB Output is correct
15 Correct 72 ms 9220 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 63 ms 9236 KB Output is correct
7 Correct 59 ms 9284 KB Output is correct
8 Correct 73 ms 9228 KB Output is correct
9 Correct 62 ms 9252 KB Output is correct
10 Correct 68 ms 9112 KB Output is correct
11 Correct 63 ms 9356 KB Output is correct
12 Correct 76 ms 9352 KB Output is correct
13 Correct 63 ms 9384 KB Output is correct
14 Correct 67 ms 9316 KB Output is correct
15 Correct 72 ms 9220 KB Output is correct
16 Correct 724 ms 38944 KB Output is correct
17 Correct 514 ms 38980 KB Output is correct
18 Correct 654 ms 38980 KB Output is correct
19 Correct 505 ms 38568 KB Output is correct
20 Correct 675 ms 38136 KB Output is correct
21 Correct 638 ms 39852 KB Output is correct
22 Correct 616 ms 39872 KB Output is correct
23 Correct 615 ms 39984 KB Output is correct
24 Correct 642 ms 39640 KB Output is correct
25 Correct 605 ms 39104 KB Output is correct