Submission #1257517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257517		medmdg	Triple Peaks (IOI25_triples)	C++20	0 / 100	2107 ms	362068 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> H;
ll n;
bool check(ll i,ll j,ll k){
  if(i<0||j<0||k<0||i>=n||j>=n||k>=n)return 0;
  ll s1[3],s2[3];
  s1[0]=(abs(j-i));
  s1[1]=(abs(k-i));
  s1[2]=(abs(j-k));
  sort(s1,s1+3);
  if(s1[0]==0)return 0;
  s2[0]=(H[i]);
  s2[1]=(H[j]);
  s2[2]=(H[k]);
  sort(s2,s2+3);
  return s1[0]==s2[0]&&s1[1]==s2[1]&&s1[2]==s2[2];
}
ll sub4(){
  ll ans=0;
  for(int i=n-1;i>1;i--){
    ll x2=i-H[i];
    if(x2<0)continue;
    ll x3=x2+H[x2],x4=i-H[x2];
    if(x3<i && i-x3==H[x3])ans++;
    if(x3!=x4)
    if(x4>x2 && x4-x2==H[x4])ans++;
  }
  return ans;
}
ll sub2(){
  ll ans=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<=i+20;j++){
      for(int k=j+1;k<n&&k<i+20;k++){
        ans+=check(i,j,k);
      }
    }
  }
  return ans;
}
ll sub3(){
  ll ans=0;
  for(ll i=0;i<n;i++){
    //Check M a b
    while(1){
      ll x2=i+H[i];
      if(x2>=n)break;
      ll x3=x2-H[x2],x4=i+H[x2];
      if(x3>i && x3-i==H[x3])ans++;
      if(x3!=x4)
      if(x4<x2 && x2-x4==H[x4])ans++;
      break;
    }
    //check a b M
    while(1){
      ll x2=i-H[i];
      if(x2<0)break;
      ll x3=x2+H[x2],x4=i-H[x2];
      if(x3<i && i-x3==H[x3])ans++;
      if(x3!=x4)
      if(x4>x2 && x4-x2==H[x4])ans++;
      break;
    }
    //check a M b
    ll l=max(0LL,i-H[i]+1);
    ll r=min(i,n-H[i]);
    for(int j=l;j<r;j++){
      ll x3=j+H[i];
      if(H[j]==i-j&&H[x3]==x3-i)ans++;
      else if(H[x3]==i-j&&H[j]==x3-i)ans++;
    }
  }
  return ans;
}
ll full(){
  ll ans=0;
  ll typ=sqrt(n);
  ll ntype=450;
  vector<vector<int>> a(n+1,vector<int>(ntype,n));
  vector<int> type(n);
  for(int i=n-1;i>=0;i--){
    if(i!=n-1){
      for(int j=0;j<ntype;j++){
        a[i][j]=a[i+1][j];
      }
    }
    type[i]=H[i]/typ;
    a[i][type[i]]=i;
  }

  for(ll i=0;i<n;i++){
    //Check M a b
    while(1){
      ll x2=i+H[i];
      if(x2>=n)break;
      ll x3=x2-H[x2],x4=i+H[x2];
      if(x3>i && x3-i==H[x3])ans++;
      if(x3!=x4)
      if(x4<x2 && x2-x4==H[x4])ans++;
      break;
    }
    //check a b M
    while(1){
      ll x2=i-H[i];
      if(x2<0)break;
      ll x3=x2+H[x2],x4=i-H[x2];
      if(x3<i && i-x3==H[x3])ans++;
      if(x3!=x4)
      if(x4>x2 && x4-x2==H[x4])ans++;
      break;
    }
    //check a M b
    ll l=max(0LL,i-H[i]+1);
    ll r=min(i,n-H[i]);
    /*for(int j=l;j<r;j++){
      ll x3=j+H[i],dt=i-j,dt2=x3-i;
      if(H[j]==dt&&H[x3]==dt2)ans++;
      else if(H[x3]==dt&&H[j]==dt2)ans++;
    }*/
    /// check o M o
    for(int j=0;j<ntype;j++){
      ll mir=i-typ*(j+1),mar=i-typ*j;
      mir=max(mir,l);
      mar=min(mar,r);
      mir=a[mir][j];
      while(mir<mar){
        ll x3=mir+H[i],dt=i-mir,dt2=x3-i;
        if(H[mir]==dt&&H[x3]==dt2)ans++;
        mir=a[mir+1][j];
      }
    }
    
    ///check x M x
    for(int j=0;j<ntype;j++){
      ll mir=i+typ*j-H[i],mar=i+typ*(j+1)-H[i];
      mar=min(mar,r);
      mir=min(mir,mar);
      mir=max(mir,l);
      mir=a[mir][j];
      while(mir<mar){
        ll x3=mir+H[i],dt=i-mir,dt2=x3-i;
        if(dt!=dt2)
        if(H[x3]==dt&&H[mir]==dt2)ans++;
        mir=a[mir+1][j];
      }
    }
  }
  return ans;
}
ll count_triples(vector<int> h) {
  n=h.size();

  H=h;
  return full();
}

vector<int> construct_range(int M, int K) {
  
  return {1,1,1};
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5