제출 #535428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535428		mario05092929	모임들 (IOI18_meetings)	C++14	17 / 100	119 ms	10720 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
typedef vector <ll> vecl;
using namespace std;
const int INF = 9;
int n,Q;
vecl ans;
int a[7500005];
struct Tree {int l,r,mx,s;}t[4000005];

Tree f(Tree l,Tree r) {
    Tree ret;
    ret.s = l.s&r.s;
    ret.l = (l.s ? l.mx+r.l : l.l);
    ret.r = (r.s ? r.mx+l.r : r.r);
    ret.mx = max({l.mx,r.mx,l.r+r.l});
    return ret;
}

void build(int x,int l,int r) {
    if(l == r) {
        if(a[l] == 1) t[x] = {1,1,1,1};
        else t[x] = {0,0,0,0};
        return;
    }
    int mid = (l + r) >> 1;
    build(x*2,l,mid), build(x*2+1,mid+1,r);
    t[x] = f(t[x*2],t[x*2+1]);
}

Tree query(int x,int l,int r,int rl,int rr) {
    if(rl > r||l > rr) return {0,0,0,0};
    if(rl <= l&&r <= rr) return t[x];
    int mid = (l + r) >> 1;
    return f(query(x*2,l,mid,rl,rr),query(x*2+1,mid+1,r,rl,rr));
}

void debug(int x,int l,int r) {
    //cout << l << " ~ " << r << " : " << t[x].x << ' ' << t[x].cnt << '\n';
    if(l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    debug(x*2,l,mid), debug(x*2+1,mid+1,r);
    t[x] = f(t[x*2],t[x*2+1]);
}

vecl minimum_costs(vec H,vec L,vec R) {
    n = H.size(), Q = L.size();
    for(int i = 0;i < n;i++) a[i+1] = H[i];
    ans.resize(Q);
    build(1,1,n);
    for(int t = 0;t < Q;t++) {
        int l = L[t]+1, r = R[t]+1;
        Tree val = query(1,1,n,l,r);
        ans[t] = 2*(r-l+1)-val.mx;
    }
    return ans;
}

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