Submission #823348

#	Time	Username	Problem	Language	Result	Execution time	Memory
823348		Dremix10	Meetings (IOI18_meetings)	C++17	0 / 100	38 ms	1700 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 1e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;

int A[N],seg[4*N];

void build(int s, int e, int idx){
    if(s==e){
        seg[idx] = A[s];
        return;
    }
    int mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}

int query(int s, int e, int idx, int qs, int qe){
    if(qs<=s && e<=qe)return seg[idx];
    if(s > qe || e < qs)return 0;
    int mid = (s+e)/2;
    return max(query(s,mid,idx*2,qs,qe),query(mid+1,e,idx*2+1,qs,qe));
}


vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) {
    int n = arr.size();
    int q = L.size();
    int i,j,k;

    vector<ll> ans(q);

    // good i is always local minima
    //if(i-1 >= x && arr[i-1] < arr[i] || i+1 <= y && arr[i+1] < arr[i])continue;
    
    int cnt = 0;

    for(i=0;i<n;i++){
        if(arr[i] == 2){
            int temp = cnt;
            int j = i-1;
            while(temp--){
                A[j] = cnt;
                j--;
            }
            cnt = 0;
            A[i] = 0;
        }
        else
            cnt++;
    }

    int temp = cnt;
    j = i-1;
            while(temp--){
                A[j] = cnt;
                j--;
            }
            cnt = 0;
            //A[i] = 0;
    
    for(i=0;i<n;i++){
        cerr<<A[i]<<" ";
    }cerr<<endl;

    build(0,n-1,1);

    for(k=0;k<q;k++){
        int x = L[k];
        int y = R[k];
        ll res = (y-x+1)*2 - query(0,n-1,1,x,y);
        
        ans[k] = res;
    }


    return ans;
}

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