Submission #1250363

#TimeUsernameProblemLanguageResultExecution timeMemory
1250363Zbyszek993개의 봉우리 (IOI25_triples)C++20
70 / 100
193 ms39024 KiB
#include "triples.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+9; const int sqr = 410; ll code_tri(ll a, ll b, ll c) { return a + b*200001LL + c*200001LL*200001LL; } vi decode_tri(ll x) { int a = x % 200001LL; x /= 200001LL; int b = x % 200001LL; x /= 200001LL; return {a,b,(int)x}; } vi L_pot[400001]; vi R_pot[400001]; ll cntL[400001]; ll cntR[400001]; int H[200001]; int n; ll ans = 0; void solve(vi& l, vi& r) { forall(it,l) { cntL[H[it]-it+200000]++; } forall(it,r) { cntR[H[it]+it]++; } rep(it,n) { ans += cntL[H[it]-it+200000]*cntR[H[it]+it]; } forall(it,l) { cntL[H[it]-it+200000]--; } forall(it,r) { cntR[H[it]+it]--; } } ll count_triples(vi H2) { unordered_set<ll> tri; n = siz(H2); rep(i,n) H[i] = H2[i]; rep(i,n) { // l-s s-r l-r if(i+H[i] < n && i+H[i]+H[i+H[i]] < n && H[i+H[i]+H[i+H[i]]] == i+H[i]+H[i+H[i]] - i) tri.insert(code_tri(i,i+H[i],i+H[i]+H[i+H[i]])); // l-s l-r s-r if(i+H[i] < n && i+H[i+H[i]] < n && H[i+H[i+H[i]]] == i+H[i+H[i]] - (i+H[i])) tri.insert(code_tri(i,i+H[i],i+H[i+H[i]])); // l-r l-s s-r if(i+H[i] < n && i+H[i]-H[i+H[i]] >= 0 && H[i+H[i]-H[i+H[i]]] == i+H[i]-H[i+H[i]] - i) tri.insert(code_tri(i,i+H[i]-H[i+H[i]],i+H[i])); // l-r s-r l-s if(i+H[i] < n && i+H[i+H[i]] < n && H[i+H[i+H[i]]] == i+H[i] - (i+H[i+H[i]])) tri.insert(code_tri(i,i+H[i+H[i]],i+H[i])); // s-r s-l r-l i = S if(i-H[i] >= 0 && i+H[i-H[i]] < n && H[i+H[i-H[i]]] == i+H[i-H[i]] - (i-H[i])) tri.insert(code_tri(i-H[i],i,i+H[i-H[i]])); } forall(it,tri) { vi v = decode_tri(it); int a = v[0]; int b = v[1]; int c = v[2]; if(!(H[a] == c-b && H[b] == c-a && H[c] == b-a)) { ans++; } } rep(i,n) { L_pot[H[i]+i].pb(i); if(i - H[i] >= 0) R_pot[i-H[i]].pb(i); } // s-r r-l s-l rep(o,n*2) { if(siz(L_pot[o]) < sqr) { forall(itL,L_pot[o]) { forall(itR,R_pot[o]) { int itS = itL + H[itR]; if(itS < n && H[itL] == itR-itS && H[itS] == itR-itL && H[itR] == itS-itL) ans++; } } } else { solve(L_pot[o],R_pot[o]); } } return ans; } vi construct_range(int M, int K) { }

Compilation message (stderr)

triples.cpp: In function 'std::vector<int> construct_range(int, int)':
triples.cpp:138:1: warning: no return statement in function returning non-void [-Wreturn-type]
  138 | }
      | ^
#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...