Submission #1159292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159292		Ak_16	Strange Device (APIO19_strange_device)	C++20	100 / 100	913 ms	47460 KiB

strange_device

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long

struct wei{
  int l;
  int r;
};
wei ar[2000005];

int gcd(int x, int y){
  if(x*y==0){return x+y;}
  if(x<y){swap(x,y);}
  return gcd(y, x%y);
}

bool cmp(wei x, wei y){
  if(x.r!=y.r){return x.r<y.r;}
  return x.l < y.l;
}

signed main() 
{
    int n,a,b;
    int n1,n2;
    int pos[2000005];
    int con[2000005];
    int ll,rr;
    cin>>n>>a>>b;
    int k = gcd(a, b+1);
    int len = a/k;
    int ans=0;
    int chk=0;
    int cur=0;
    int don=0;
    
    ar[0].l = -1;
    ar[0].r = -1;
    pos[0]=0;
    
    if(b > (1e18)/len){len = 1e18 + 5LL;}
    
    else {len *= b;}
    
    for(int i=1; i<=n; i++){
      cin>>n1>>n2;
      if(n2-n1+1>=len){chk=1;}
      n1 %= len;
      n2 %= len;
      if(n1<=n2){
        cur++;
        ar[cur].l = n1;
        ar[cur].r = n2;
      }
      else {
        cur++;
        ar[cur].l = 0;
        ar[cur].r = n2;
        cur++;
        ar[cur].l = n1;
        ar[cur].r = len-1;
      }
    }
    
    sort(ar+1, ar+cur+1, cmp);
    ar[0].l = -1;
    ar[0].r = -1;
    
    for(int i=1; i<=cur; i++){
      
      while(don>=1){
        n1 = pos[don];
        if(ar[i].l <= ar[n1].l){
          ans -= con[don];
          con[don]=0;
          don--;
        }
        else {break;}
      }
      
      don++;
      pos[don]=i;
      con[don] = ar[i].r - max(ar[i].l-1, ar[pos[don-1]].r);
      ans += con[don];
      
      
    }
    if(chk==1){cout<<len<<endl;}
    else {cout<<ans<<endl;}
    
    
    
    
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30