Submission #1095191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095191		0pt1mus23	Janjetina (COCI21_janjetina)	C++14	35 / 110	262 ms	5412 KiB

Main

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

#define int long long
#define endl '\n'
#define ins insert
#define pb push_back
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<  
const int   mod = 1e9+7 ,
            sze= 1e5 +23 ,
            inf = INT_MAX ,
            L = 31 ;

int arr[sze];
int ans=0;
int T[sze +23];
int k;
vector<pair<int,int>> event;

void upd(int node,int x){
    for(++node;node<=sze;node += (node & -node)){
        T[node]+=x;
    }
}
int qry(int node){
    int sum=0;
    for(++node;node>0;node -= (node & -node)){
        sum+=T[node];
    }
    return sum;
}

void kullan(int vur){
    sort(all(event));
    for(auto v:event){
        ans+=vur * qry(v.first - v.second - k);
        upd(v.second,1);
    }
    for(auto v:event){
        upd(v.second,-1);
    }

    event.clear();
}
void fener(int l,int r){
    if(l>=r){
        return;
    }
    int mx = 0;
    int mid = (l+r)/2;
    fener(l,mid);
    fener(mid+1,r);
    for(int i = mid;i>=l;i--){
        event.pb({mx,mid - i});
        mx=max(mx,arr[i-1]);
    }
    mx=0;
    for(int i=mid;i<r;i++){
        mx=max(mx,arr[i]);
        event.pb({mx,i - mid +1});
    }
    kullan(1);
    mx =0;
    for(int i =mid;i>=l;i--){
        event.pb({mx, mid  - i});
        mx=max(mx,arr[i-1]);
    }
    kullan(-1);
    mx=0;
    for(int i = mid;i<r;i++){
        mx=max(mx,arr[i]);
        event.pb({mx, i - mid+1});
    }
    kullan(-1);
}   

void opt1z(){
    int n;
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        arr[i]=w;
    }
    fener(1,n);
    cout<<ans*2LL<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60