Submission #1188317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188317		qs1	Bouquet (EGOI24_bouquet)	C++20	100 / 100	113 ms	9160 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define mt make_tuple
#define mp make_pair

int main(){
  lli x,i,a,b,mx=0,m,n;
  cin>>x;
  priority_queue<pair<lli,lli>>pq;
  vector<tuple<lli,lli,lli>>q(x);//(from the one who comes, the one who goes, itself)
  vector<lli>v(x+2,0),l={0,999999999};
  for(lli i=1;i<=x;i++){
    cin>>a>>b;
    a++;
    b++;
    if(a>i)a=i;
    if(b+i>x)b=x-i+1;
    a=i-a;
    b=i+b;
    q[i-1]=mt(a,b,i);
  }
  sort(q.begin(),q.end());
  for(auto t:q){
    a=get<0>(t);
    b=get<1>(t);
    i=get<2>(t);
    while(!pq.empty()&&999999999-pq.top().first<=a){
      n=v[999999999-pq.top().first];
      m=pq.top().second;
      if(n+1==l.size()){
        l[n]=m;
        l.push_back(999999999);
      }
      else l[n]=min(l[n],m);
      pq.pop();
    }
    m=upper_bound(l.begin(),l.end(),i)-l.begin()-1;
    v[i]=m+1;
    pq.push(mp(999999999-i,b));
    mx=max(mx,v[i]);
  }
  cout<<mx<<endl;
}

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