Submission #709728

#	Time	Username	Problem	Language	Result	Execution time	Memory
709728		groshi	Election (BOI18_election)	C++17	100 / 100	568 ms	27640 KiB

election

#include<iostream>
#include<algorithm>
using namespace std;
pair<pair<int,int>,pair<int,int> > drzewo[2000000];///0 -> suma, 1 -> lewo, 2 -> prawo, 3 -> wynik
int pot=1;
pair<pair<int,int>,pair<int,int> > lacz(pair<pair<int,int>,pair<int,int> > a,pair<pair<int,int>,pair<int,int> > b)
{
    pair<pair<int,int>,pair<int,int> > para={{0,0},{0,0}};
    para.first.first=a.first.first+b.first.first;
    para.first.second=max(a.first.second,a.first.first+b.first.second);
    para.second.first=max(b.second.first,b.first.first+a.second.first);
    para.second.second=max({a.first.second+b.second.first,a.first.first+b.second.second,a.second.second+b.first.first});
    return para;
}
pair<pair<int,int>,pair<int,int> > zapp(int x,int l,int r,int a,int b)
{
    if(l>b || r<a)
        return {{0,0},{0,0}};
    if(a<=l && r<=b)
        return drzewo[x];
    int mid=(l+r)/2;
    auto mam1=zapp(x*2,l,mid,a,b);
    auto mam2=zapp(x*2+1,mid+1,r,a,b);
    return lacz(mam1,mam2);
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,x,y;
    cin>>n;
    string s;
    cin>>s;
    while(pot<=n)
        pot*=2;
    pot--;
    for(int i=0;i<n;i++)
        if(s[i]=='T')
            drzewo[i+pot+1].first.first=drzewo[i+pot+1].first.second=drzewo[i+pot+1].second.first=drzewo[i+pot+1].second.second=1;
        else drzewo[i+pot+1].first.first=-1;
    for(int i=pot;i>=1;i--)
        drzewo[i]=lacz(drzewo[i*2],drzewo[i*2+1]);
    int zap;
    cin>>zap;
    while(zap--)
    {
        int x,y;
        cin>>x>>y;
        cout<<zapp(1,pot+1,pot*2+1,x+pot,y+pot).second.second<<"\n";
    }
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int32_t main()':
election.cpp:31:11: warning: unused variable 'x' [-Wunused-variable]
   31 |     int n,x,y;
      |           ^
election.cpp:31:13: warning: unused variable 'y' [-Wunused-variable]
   31 |     int n,x,y;
      |             ^

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