제출 #1252096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252096		idiotcomputer	3개의 봉우리 (IOI25_triples)	C++20	25 / 100	80 ms	48832 KiB

triples

//IOI 2025 Day 1 Problem B 

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define sz(x) (int) (x).size()
#define vi vector<int>
#define f first
#define s second 
#include "triples.h"



long long count_triples(vi h){

    int n = sz(h);

    ll res = 0;
    for (int i = 0; i < n; i++){
        //largest right
        if (h[i] > i) continue;
        int c = h[i-h[i]];
        if (c < h[i]){
            if (h[i-h[i]+c] == h[i] - c) res++;
            if (c+c != h[i] && h[i-c] == h[i] - c) res++;
        }

        //largest center, right is right 
        c = h[i-h[i]];
        if (c > h[i] && h[i-c] == c - h[i]) res++;        
    }

    for (int i = 0; i < n; i++){
        //largest left
        if (h[i]+i >= n) continue;
        int c = h[i+h[i]];
        if (c < h[i]){
            if (h[i+h[i]-c] == h[i]-c) res++;
            if (c+c != h[i] && h[i+c] == h[i]-c) res++;
        }
    }
    //cout << res << '\n';
    //largest center, left is right and right is left
    //i-h[i], i+h[i]
    set<int> lef[2*n];
    set<int> rig[2*n];

    for (int i = 0; i < n; i++) rig[h[i]+i].insert(i);
    for (int i = 0; i < n; i++){
        rig[h[i]+i].erase(i);
        int i1 = i-h[i]+n;
        int i2 = h[i]+i;
       // cout << i << " " << i1 << " " << i2 << '\n';
        if (sz(lef[i1]) < sz(rig[i2])){
            //cout << "Checkign left\n";
            for (int j : lef[i1]) if (i+h[j] < n && h[i+h[j]] == h[i] - h[j] && h[j] * 2 != h[i]) res++;
        } else {
            //cout << "Checking right " << *rig[i2].begin() << '\n';
            for (int j : rig[i2]) if (i-h[j] >= 0 && h[i-h[j]] == h[i] - h[j] && h[j] * 2 != h[i]) res++;
        }
        lef[i1].insert(i);
    }
    return res;
}

vi construct_range(int m, int k){
    return {};
}

/*
namespace {

void run_part1() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> H(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &H[i]));
  fclose(stdin);

  long long T = count_triples(H);

  printf("%lld\n", T);
  fclose(stdout);
}

void run_part2() {
  int M, K;
  assert(2 == scanf("%d %d", &M, &K));
  fclose(stdin);

  std::vector<int> H = construct_range(M, K);

  int N = H.size();
  printf("%d\n", N);
  for (int i = 0; i < N; i++)
    printf("%d%c", H[i], " \n"[i + 1 == N]);
  fclose(stdout);
}

} // namespace

int main() {
  int part;
  assert(1 == scanf("%d", &part));
  if (part == 1)
    run_part1();
  else if (part == 2)
    run_part2();

  return 0;
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 0 / 10
• Subtask 4: 11 / 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