Submission #489648

#	Time	Username	Problem	Language	Result	Execution time	Memory
489648		MarkoDimi3c	Election (BOI18_election)	C++14	0 / 100	8 ms	204 KiB

election

#include<bits/stdc++.h>
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int main(){

int n;
cin >>n;
vector<char> v(n);
vector<int> t;
vector<int> c;
int tt=0;
int tc=0;
bool proslit = false;
bool proslic = false;
cin >> v[0];

if(v[0] == 'T'){
    proslit=true;
    tt++;
}
else{
    proslic=true;
    tc++;
}
bool prvitony = proslit;
for(int i = 1; i < n; i++){
        cin>>v[i];
        if(v[i]=='T'){
            if(proslit == true){
                tt++;
            }
            else{
                if(tt >0)t.push_back(tt);
                tt=1;
            }
            proslic=false;
            proslit=true;
        }
        else{
          if(proslic == true){
                tc++;
            }
            else{
                if(tc>0)c.push_back(tc);
                tc=1;
            }
            proslit=false;
            proslic=true;
        }

}
if(tc>0)c.push_back(tc);
if(tt>0)t.push_back(tt);


vector<pair<int,bool>> g;
if(prvitony){
    if(t.size()>0)g.push_back(make_pair(t[0],true));
    if(c.size()>0)g.push_back(make_pair(c[0]+g[0].first,false));
    for(int i = 1; i < c.size();i++){
        g.push_back(make_pair(t[i]+g[2*i-1].first,true));
        g.push_back(make_pair(c[i]+g[2*i].first,false));
    }
    if(t.size()>c.size()&& t.size()>1)g.push_back(make_pair(t[t.size()-1]+g[g.size()-1].first,true));
}
else{
    if(c.size()>0)g.push_back(make_pair(c[0],false));
    if(t.size()>0)g.push_back(make_pair(t[0]+g[0].first,true));
    for(int i = 1; i < t.size();i++){
        g.push_back(make_pair(c[i]+g[2*i-1].first,false));
        g.push_back(make_pair(t[i]+g[2*i].first,true));
    }
    if(c.size()>t.size()&& c.size()>1)g.push_back(make_pair(c[c.size()-1]+g[g.size()-1].first,false));
}
int q;
cin >> q;
int l,r;
while(q--){
    cin >> l >> r;
    vector<int>kill;
    int i = 0;
    while(g[i].first<l){
        i++;
        if(i==g.size())break;
    }
    int j = 0;
    while(g[j].first<r){
        j++;
        if(j==g.size())break;
    }
    if(i == j){
        if(g[i].second == true)kill.push_back(r-l+1);
    }
    else{
    int levi1 = g[i].first-l+1;
    bool levi2 = g[i].second;
    int desni1=r-g[j-1].first;
    bool desni2=g[j].second;

    bool toni=levi2;
    int capwins = 0;
    if(toni){
        kill.push_back(levi1);

    }
    else capwins+=levi1;
    toni=!toni;
    for(int k = i+1; k < j;k++){
        if(toni){
            if(capwins>=g[k].first-g[k-1].first){
                capwins-=g[k].first-g[k-1].first;
                kill.push_back(0);
            }
            else{
                kill.push_back(g[k].first-g[k-1].first-capwins);
                capwins=0;
            }
            toni=!toni;
        }
        else{
              capwins+=g[k].first-g[k-1].first;
              toni=!toni;

        }
    }
    if(toni){
        if(desni1>capwins){
            kill.push_back(desni1-capwins);
                capwins=0;
        }
        else kill.push_back(0);
    }
    int u = 1;
    capwins = 0;
    if(toni){
        kill[kill.size()-u]=max(kill[kill.size()-u],desni1);
        u++;
    }
    else capwins+=desni1;
    toni=!toni;

    for(int k = j-1; k > i;k--){
        if(toni){
            if(capwins>=g[k].first-g[k-1].first){
                capwins-=g[k].first-g[k-1].first;
                kill[kill.size()-u]=max(kill[kill.size()-u],0);
                u++;
            }
            else{
                kill[kill.size()-u]=max(kill[kill.size()-u],g[k].first-g[k-1].first-capwins);
                capwins=0;
                u++;
            }
            toni=!toni;
        }
        else{
              capwins+=g[k].first-g[k-1].first;
              toni=!toni;
        }
    }

    if(toni){
        kill[kill.size()-u]=max(kill[kill.size()]-u,levi1);
        kill.push_back(levi1);

    }

}
    int h = 0;
    for(int i = 0; i < kill.size();i++)h+=kill[i];
    cout << h << endl;
}
return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 1; i < c.size();i++){
      |                    ~~^~~~~~~~~~
election.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i < t.size();i++){
      |                    ~~^~~~~~~~~~
election.cpp:86:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if(i==g.size())break;
      |            ~^~~~~~~~~~
election.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if(j==g.size())break;
      |            ~^~~~~~~~~~
election.cpp:100:10: warning: unused variable 'desni2' [-Wunused-variable]
  100 |     bool desni2=g[j].second;
      |          ^~~~~~
election.cpp:172:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for(int i = 0; i < kill.size();i++)h+=kill[i];
      |                    ~~^~~~~~~~~~~~~

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