Submission #1254196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254196		KLPP	Triple Peaks (IOI25_triples)	C++20	70 / 100	1641 ms	87320 KiB

triples

#include "triples.h"
#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
int h[1000000];
int n;
vector<int> Pts[1000000];
set<int> S[1000000];
bool test(int a, int b, int c){
  if(0<=a && a<b && b<c && c<n){
    vector<int> X={b-a,c-a,c-b};
    sort(X.begin(),X.end());
    vector<int> Y={h[a],h[b],h[c]};
    sort(Y.begin(),Y.end());
    rep(i,0,3){
      if(X[i]!=Y[i])return false;
    }
    // cout<<a<<" "<<b<<" "<<c<<endl;
    return true;
  }return false;
}
long long count_triples(std::vector<int> H) {
  
  
  
  lld ans=0;
  n=H.size();
  rep(i,0,n)h[i]=H[i];
  rep(i,0,3*n)S[i].clear(),Pts[i].clear();
  
  // lld ans2=0;
  // rep(a,0,n){
    // rep(b,a+1,n){
      // rep(c,b+1,n){
        // int res=test(a,b,c);
        // ans2+=res;
      // }
    // }
  // }
  
  
  
  rep(i,0,n){
    int Nx=i+H[i];
    if(Nx<n){
      ans+=test(i,i+H[Nx],Nx);
      if(i+H[Nx]!=Nx-H[Nx]){
        ans+=test(i,Nx-H[Nx],Nx);
      }
    }
  }
  rep(i,0,n){
    int Pr=i-H[i];
    if(Pr>=0){
      ans+=test(Pr,Pr+H[Pr],i);
      if(Pr+H[Pr]!=i-H[Pr]){
        ans+=test(Pr,i-H[Pr],i);
      }
    }
  }
  
  rep(i,0,n){
    int Nx=i+H[i];
    if(H[Nx]!=2*H[i]){
      ans+=test(i,Nx,i+H[Nx]);
    }
  }
  
  // vector<pair<int,int> >P;
  rep(i,0,n){
    int X=i-H[i]+n;
    int Y=i+H[i]+n;
    if(0<=X && X<3*n && 0<=Y && Y<3*n)Pts[X].push_back(Y);
  }
  
  // int A=0;
  // trav(a,P){
    // trav(b,P){
      // trav(c,P){
        // if(a!=b && b!=c && a!=c){
          // if(b.first==a.first && b.second==c.second && a.second==c.first){
            // A++;
            // cout<<"2 "<<(a.first+a.second)/2<<" "<<(b.first+b.second)/2<<" "<<(c.first+c.second)/2<<endl;
          // }
        // }
      // }
    // }
  // }
  // cout<<A<<endl;
  
  rep(i,0,3*n){
    trav(a,Pts[i]){
      if(S[i].size()<S[a].size()){
        trav(b,S[i]){
          ans+=(S[a].find(b)!=S[a].end());
        }
      }else{
        trav(b,S[a]){
          ans+=(S[i].find(b)!=S[i].end());
        }
      }
    }
    
    trav(a,Pts[i]){
      S[a].insert(i);
    }
  }
  // cout<<ans<<" "<<ans2<<endl;
  return ans;
}

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

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 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