oj.uz

Submission #1095190

# Submission time Handle Problem Language Result Execution time Memory
1095190 2024-10-01T14:06:55 Z 0pt1mus23 Janjetina (COCI21_janjetina) C++14
0 / 110
 1 ms 460 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -