Submission #1257326

#TimeUsernameProblemLanguageResultExecution timeMemory
1257326medmdg3개의 봉우리 (IOI25_triples)C++20
45.29 / 100
2095 ms2736 KiB
#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 count_triples(vector<int> h) { n=h.size(); H=h; return sub3(); } vector<int> construct_range(int M, int K) { vector<int> a; for(int i=0;i<M;i++){ if(i%3)a.push_back(1); else a.push_back(2); } return a; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...