Submission #1250363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250363		Zbyszek99	Triple Peaks (IOI25_triples)	C++20	70 / 100	193 ms	39024 KiB

triples

#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 | }
      | ^

• 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