Submission #1092196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092196		naneosmic	Bouquet (EGOI24_bouquet)	C++14	100 / 100	88 ms	9548 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
signed main(){    
  int n;    
  cin>>n;    
  vector<int>l(n),r(n),lowerbound,MAX,vals;    
  for(int i=0;i<n;i++){        cin>>l[i]>>r[i];    
                      }    
  int ans=1;    
  MAX.push_back(1);    lowerbound.push_back(r[0]);    vals.push_back(0);    
  for(int i=1;i<n;i++){       
    int lower=i-l[i]-1;        pair<int,int>NEW;        pair<int,int>OLD;        OLD.first=MAX[i-1];        OLD.second=lowerbound[i-1];        if(lower<0){            NEW.first=0;            NEW.second=i+r[i];        }else{            NEW.second=i+r[i];            if(OLD.first==1){                if(lowerbound[lower]>=i)NEW.first=0;                else NEW.first=1;            }else{                if(MAX[lower]<=OLD.first-2)NEW.first=OLD.first-2;                else{                    if(MAX[lower]==OLD.first-1){                        if(lowerbound[lower]>=i)NEW.first=OLD.first-2;                        else NEW.first=OLD.first-1;                    }else{                        if(lowerbound[lower]>=i){                            if(lowerbound[vals[vals.size()-2]]>=i)NEW.first=OLD.first-2;                            else NEW.first=OLD.first-1;                        }else{                            NEW.first=OLD.first;                        }                    }                }            }        }        NEW.first++;        if(NEW.first<OLD.first){            MAX.push_back(OLD.first);            lowerbound.push_back(OLD.second);            vals[vals.size()-1]++;        }else if(NEW.first==OLD.first){            NEW.second=min(NEW.second,OLD.second);            MAX.push_back(NEW.first);            lowerbound.push_back(NEW.second);            vals[vals.size()-1]++;        }else{            MAX.push_back(NEW.first);            lowerbound.push_back(NEW.second);            vals.push_back(i);            ans++;        }    }    cout<<ans<<endl;}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30