Submission #1269764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269764		vietbachleonkroos2326	3개의 봉우리 (IOI25_triples)	C++20	4.76 / 100	22 ms	16060 KiB

triples

#include<bits/stdc++.h>
#include "triples.h"
#define TIME (1.0* clock()/CLOCKS_PER_SEC)
#define pb push_back
#define eb emplace_back
#define id1 (id<<1)
#define id2 (id<<1)|1
#define ll long long
//#define ii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>> 
#define vl vector<long long>
#define vll vector <pair<ll,ll>>
#define li pair<long long,int>
#define vil vector <pair<int,ll>>
#define db double
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i <=(b); i++)
#define F0R(i, a) FOR(i, 0, a-1)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)
#define ALL(x) (x).begin(),(x).end()
#define pq priority_queue <li, vector <li>, greater <li>> 
using namespace std;
const int maxn=1e6;
//const int MOD=1e9+7;
//const int MOD=998244353;
//const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};


long long count_triples(std::vector<int> H){
    int N = (int)H.size();
    if(N < 3) return 0;
    // plus[p] = indices i with i + H[i] == p
    // minus[p] = indices i with i - H[i] == p
    vector<vector<int>> plus(N), minus(N);
    for(int i = 0; i < N; ++i){
        int p = i + H[i];
        if(p >= 0 && p < N) plus[p].push_back(i);
        int q = i - H[i];
        if(q >= 0 && q < N) minus[q].push_back(i);
    }

    vector<int> cnt(N+1, 0);
    vector<int> touched;
    ll ans = 0;

    for(int j = 0; j < N; ++j){
        // case 1: i = j - H[j], k in minus[j], check H[i] == H[j] + H[k]
        int i = j - H[j];
        if(i >= 0){
            for(int k : minus[j]){
                if(H[i] == H[j] + H[k]) ans++;
            }
        }

        // case 3: k = j + H[j], i in plus[j], check H[k] == H[i] + H[j]
        int k = j + H[j];
        if(k < N){
            for(int ii : plus[j]){
                if(H[k] == H[ii] + H[j]) ans++;
            }
        }

        // case 2: j is the largest (a+b). need pairs (i in plus[j], k in minus[j]) with H[i] + H[k] == H[j]
        auto &L = plus[j];
        auto &R = minus[j];
        if(!L.empty() && !R.empty()){
            if(L.size() <= R.size()){
                for(int ii : L){
                    int v = H[ii];
                    if(v >= 0 && v <= N) {
                        if(cnt[v] == 0) touched.push_back(v);
                        cnt[v]++;
                    }
                }
                for(int kk : R){
                    int need = H[j] - H[kk];
                    if(need >= 0 && need <= N) ans += cnt[need];
                }
            } else {
                for(int kk : R){
                    int v = H[kk];
                    if(v >= 0 && v <= N) {
                        if(cnt[v] == 0) touched.push_back(v);
                        cnt[v]++;
                    }
                }
                for(int ii : L){
                    int need = H[j] - H[ii];
                    if(need >= 0 && need <= N) ans += cnt[need];
                }
            }
            for(int v : touched) cnt[v] = 0;
            touched.clear();
        }
    }

    return ans;
}

vector<int> construct_range(int M, int K){
    if(M < 3) {
        return vector<int>(3,1); 
    }

    int s_size = max(2, (int)(sqrt((double)M) * 2.0));
    s_size = min(s_size, M);

    vector<int> Hmap(M, -1);
    vector<char> used(M, 0);
    int filled = 0;
    int maxUsedIdx = -1;

    for(int a = 0; a < s_size && filled < M; ++a){
        for(int b = a+1; b < s_size && filled < M; ++b){
            int i = a + b;      
            if(i >= M) continue; 
            if(used[i]) continue;
            int h = b - a;      
            if(h <= 0) continue;
            Hmap[i] = h;
            used[i] = 1;
            ++filled;
            if(i > maxUsedIdx) maxUsedIdx = i;
        }
    }

    int a_start = s_size;
    int s_limit = min(M, (int)max( (double)s_size*4.0, (double)s_size+500.0 ));
    for(int a = a_start; a < s_limit && filled < M; ++a){
        for(int b = 0; b < a && filled < M; ++b){
            int i = a + b;
            if(i >= M) continue;
            if(used[i]) continue;
            int h = a - b;
            if(h <= 0) continue;
            Hmap[i] = h;
            used[i] = 1;
            ++filled;
            if(i > maxUsedIdx) maxUsedIdx = i;
        }
    }

    if(filled < M){
        int extra_limit = min(M, 2000);
        for(int a = 0; a < extra_limit && filled < M; ++a){
            for(int b = a+1; b < extra_limit && filled < M; ++b){
                int i = a + b + 1; 
                if(i >= M) continue;
                if(used[i]) continue;
                int h = b - a;
                if(h <= 0) continue;
                Hmap[i] = h;
                used[i] = 1;
                ++filled;
                if(i > maxUsedIdx) maxUsedIdx = i;
            }
        }
    }

    int N;
    if(maxUsedIdx == -1){
        N = min(3, M);
        return vector<int>(N, 1);
    } else {
        N = max(3, maxUsedIdx + 1);
        if(N > M) N = M;
    }

    vector<int> H(N, 1);
    for(int i = 0; i < N; ++i){
        if(used[i]){
            int hv = Hmap[i];
            if(hv <= 0) hv = 1;
            if(hv >= N) hv = N-1;
            H[i] = hv;
        } else {
            H[i] = 1;
        }
    }

    for(int i = 0; i < N; ++i){
        if(H[i] < 1) H[i] = 1;
        if(H[i] > N-1) H[i] = N-1;
    }

    return H;
}

• 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: 3.6667 / 5
• Subtask 8: 0.83 / 5
• Subtask 9: 0.2358 / 5
• Subtask 10: 0.0148 / 5
• Subtask 11: 0.0095 / 5
• Subtask 12: 0.0022 / 5