Submission #836976

#	Time	Username	Problem	Language	Result	Execution time	Memory
836976		7mody	Meetings (IOI18_meetings)	C++17	0 / 100	34 ms	1876 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct segtree{
    struct node{
        int l,r;
        int vl,vr;
        int mx;
    };
    vector<node> tree;
    int size=1;

    ll op(ll x,ll y){
        return max(x,y);
    }

    int getnode(int n){
        return n+size;
    }

    void build(vector<int> arr){
        while(size< arr.size()) size*=2;
        tree.resize(size*2);
        for(int i=0; i < size;i++){
            tree[i+size].l=i;
            tree[i+size].r=min(i,(int)arr.size()-1);
            tree[i+size].vl=(arr[i]==1);
            tree[i+size].vr=(arr[i]==1);
            tree[i+size].mx=(arr[i]==1);
        }
        for(int i=size-1;i>=1;i--){
            tree[i].l=tree[i*2].l;
            tree[i].r=tree[i*2+1].r;
            if(tree[i*2].vl==tree[i*2].r - tree[i*2].l + 1){
                tree[i].vl=tree[i*2].vl+tree[i*2+1].vl;
            } else{
                tree[i].vl=tree[i*2].vl;
            } if(tree[i*2+1].vr==tree[i*2 + 1].r - tree[i*2 + 1].l + 1){
                tree[i].vr=tree[i*2+1].vr+tree[i*2].vr;
            } else{
                tree[i].vr=tree[i*2+1].vr;
            }
            tree[i].mx=max({tree[i].vl,tree[i].vr,tree[i*2].vr + tree[i*2+1].vl});
        }
    }

    int getr(int left,int mxr){
        int curr=getnode(left);
        int val=0;
        while(curr && tree[curr].mx==tree[curr].r - tree[curr].l + 1 && tree[curr].r <mxr){
            int prev=curr;
            curr/=2;
            if(tree[curr].r > mxr){
                return tree[prev].vl + getr(tree[prev].r+1, mxr);
            }
        }
        val=min(tree[curr].vl,mxr - left + 1);
        return val;
    }

    int getl(int right,int mxl){
        int curr=getnode(right);
        int val=0;
        while(curr && tree[curr].mx==tree[curr].r - tree[curr].l + 1 && tree[curr].l <mxl){
            int prev=curr;
            curr/=2;
            if(tree[curr].l < mxl){
                return tree[prev].vr + getr(tree[prev].l-1, mxl);
            }
        }
        val=min(tree[curr].vr,right - mxl + 1);
        return val;
    }

    int get(int L,int R,int node,int mxl,int mxr){
 
        if(tree[node].r<L || tree[node].l > R) return 0;
 
        if(tree[node].l >=L && tree[node].r <=R){

            if(L== tree[node].l && R==tree[node].r) return tree[node].mx;
            if(tree[node].r - tree[node].l + 1 == tree[node].mx){
                if(L==tree[node].l) return tree[node].mx + getr(tree[node].r + 1,mxr);
                if(R==tree[node].r) return tree[node].mx + getl(tree[node].l - 1,mxl);
                return tree[node].mx + getl(tree[node].l - 1,mxl) + getr(tree[node].r + 1,mxr);
            } else{
                if(L==tree[node].l) return op(tree[node].vr + getr(tree[node].r + 1,mxr),tree[node].mx);
                if(R==tree[node].r) return op(tree[node].vl + getl(tree[node].l - 1,mxl),tree[node].mx);
                return max({tree[node].mx,tree[node].vl + getl(tree[node].l - 1,mxl),tree[node].vr + getr(tree[node].r + 1,mxr)});
            }
        }
        return op(get(L,R,node*2,mxl,mxr) , get(L,R,node*2+1,mxl,mxr));
    }

    void out(){
        for(node x : tree){
            cout << x.l << ' ' << x.r << "   ";
        }
        cout << endl;
    }
};

vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
    int q=L.size();
    segtree arr;
    arr.build(H);
    vector<ll> ans(q);
    for(int i=0;i<q;i++){
        int l=L[i];
        int r=R[i];
        int curr=arr.get(l,r,1,l,r);
        ans[i]=((r-l+1) *2) - curr ;
    }
    return ans;
}

// void solve(){
//     int n; cin >> n;
//     int q; cin >> q;
//     vector<int> temp(n);
//     vector<int> L(q),R(q);
//     for(int i=0; i < n;i++) cin >> temp[i];
//     for(int i=0; i < q;i++) cin >> L[i] >> R[i];
//     vector<ll> ans=minimum_costs(temp,L,R);
//     for(auto c : ans) cout << c << endl;
// }

// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie(0);
//     cout.tie(0);
//     int t=1;
//     // cin >> t;
//     while(t--) solve();
//     return 0;
// }

Compilation message (stderr)

meetings.cpp: In member function 'void segtree::build(std::vector<int>)':
meetings.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         while(size< arr.size()) size*=2;
      |               ~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40