Submission #1254522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254522		garam1732	3개의 봉우리 (IOI25_triples)	C++20	0 / 100	2095 ms	20552 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], RD[MAXN];
long long count_triples(std::vector<int> H) {
    int n = H.size();
    // for(int i=0; i<n; i++) {
    //     if(i+arr[i]<n) L[i+arr[i]].push_back(i);
    //     if(i-arr[i]>=0) R[i-arr[i]].push_back(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=i-1, k=j+H[i]; j>=0 && k<n && k>i; j--, k--) {
            if(i-j == H[j] && k-i == H[k]) cnt++;
        }
    } for(int i=0; i<n; i++) {
        for(int j=i-1, k=j+H[i]; j>=0 && k<n && k>i; j--, k--) {
            if(i-j == H[k] && k-i == H[j]) 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: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 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