Submission #1254585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254585		garam1732	Triple Peaks (IOI25_triples)	C++20	70 / 100	835 ms	48964 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*2;
const ll MOD = 1e9+7;
const ll INF = 1e9+10;

vector<int> LU[MAXN], RU[MAXN];
vector<int> LD[MAXN*2], RD[MAXN*2];
long long count_triples(std::vector<int> H) {
    int n = H.size();
    for(int i=0; i<n; i++) {
        if(i+H[i]<n) LU[i+H[i]].push_back(i);
        if(i-H[i]>=0) RU[i-H[i]].push_back(i);
    }

    for(int i=0; i<n; i++) {
        LD[H[i]-i+MAXN].push_back(i);
        RD[H[i]+i].push_back(i);
    } for(int i=0; i<MAXN*2; i++) {
        sort(all(LD[i])); sort(all(RD[i]));
    }

    ll cnt=0;
    for(int i=0; i<n; i++) {
        int j = i-H[i];
        if(j >= 0) {
            if(i+H[j]<n && H[i+H[j]] == H[i]+H[j]) cnt++;
            if(i<j+H[j] && j+H[j]<n && H[j+H[j]] == H[j]-H[i]) cnt++;
        }

        int k = i+H[i];
        if(k < n) {
            if(i-H[k]>=0 && H[i-H[k]] == H[i]+H[k]) cnt++;
            if(k-H[k]<i && k-H[k]>=0 && H[k-H[k]] == H[k]-H[i]) cnt++;
        }

        if(j>=0 && k<n) {
            if(H[j]+H[k] == 3*H[i] && abs(H[j]-H[k]) == H[i]) cnt--;
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0, k=0; j<LU[i].size(); j++) {
            while(k<RU[i].size() && RU[i][k] < LU[i][j]+H[i]) k++;
            if(k<RU[i].size() && RU[i][k] == LU[i][j]+H[i]) cnt++;
        }
    } for(int i=0; i<n; i++) {
        int rd = H[i]+i, ld = H[i]-i+MAXN;
        if(LD[ld].size() < RD[rd].size()) {
            for(int x:LD[ld]) {
                if(x>=i || i>=x+H[i]) continue;
                if(lbd(RD[rd],x+H[i])!=ubd(RD[rd],x+H[i])) cnt++;
            }
        } else {
            for(int x:RD[rd]) {
                if(x-H[i]>=i || i>=x) continue;
                if(lbd(LD[ld],x-H[i])!=ubd(LD[ld],x-H[i])) cnt++;
            }
        }
    } for(int i=0; i<n; i++) {
        if(H[i]%2==0) {
            int j=i-H[i]/2, k=i+H[i]/2;
            if(j>=0 && k<n && H[j]==H[i]/2 && H[k]==H[i]/2) cnt--;
        }
    } return cnt;
}

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