Submission #1309374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309374		Faisal_Saqib	Triple Peaks (IOI25_triples)	C++20	70 / 100	1227 ms	20656 KiB

triples

#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <set>
#include "triples.h"
using namespace std;
typedef long long ll;
std::vector<int> construct_range(int M, int K)
{
    return {};
}
const int N=1e6+10;
vector<int> pos[N],pos1[N];
long long count_triples(std::vector<int> h)
{
    ll ans=0;
    ll n=h.size();
    for(int i=0;i<n;i++)pos[i].clear(),pos1[i].clear();
    // Case 1
    //       h[i] = k-i
    for(int i=0;i<n;i++)
    {
        // for(int k=i+2;k<n;k++)
        int k=i+h[i];
        if(k<n)
        {
            set<int> pj;
            pj.insert(i+h[k]);
            pj.insert(k-h[k]);
            for(auto&j:pj)
            {
                if(i<j and j<k and h[j]+h[k] == h[i])
                {
                    ans++;
                }
            }
        }
    }

    // Case 2
    //       h[k] = k-i
    for(int k=0;k<n;k++)
    {
        int i=k-h[k];
        if(i>=0)
        {
            set<int> pj;
            pj.insert(i+h[i]);
            pj.insert(k-h[i]);
            for(auto&j:pj)
            // for(auto j:pj)
            {
                if(i<j and j<k and h[j]+h[i] == h[k])
                {
                    ans++;
                }
            }
        }
    }

    for(int i=0;i<n;i++)
    {
        int v=i+h[i];
        if(0<=v and v<n)
        {
            pos[v].push_back(i);
        }
        v=i-h[i];
        if(0<=v and v<n)
        {
            pos1[v].push_back(i);
        }
    }
    for(int v=0;v<n;v++)
    {
        for(int&k:pos1[v])
        {
            for(int&i:pos[v])
            {
                if(i>=k)continue;
                set<int> pj;
                pj.insert(i+h[i]);
                pj.insert(i+h[k]);
                for(auto&j:pj)
                {
                    if(i<j and j<k and h[j]==k-i)
                    {
                        ans++;
                    }
                }
            }
        }
    }
    return ans;
}

• 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