Submission #33535

#	Time	Username	Problem	Language	Result	Execution time	Memory
33535		top34051	Ancient Books (IOI17_books)	C++14	0 / 100	0 ms	17652 KiB

books

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

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1000005;
const int inf = 1000005;

int n;
int sz[2];
long long val[2][maxn];
vector<pii> p[2];
set<int> a[2];

bool cmp(pii x,pii y) {
    if(x.Y==y.Y) return x.X>y.X;
    return x.Y>y.Y;
}

bool cmp2(long long x,long long y) {
    return x>y;
}

void get(int i) {
    sort(p[i].begin(),p[i].end(),cmp);
    for(auto t : p[i]) {
        auto it = a[i].lower_bound(t.Y);
        if(it==a[i].end()) val[i][sz[i]++] = t.Y;
        else a[i].erase(it);
        a[i].insert(t.X);
    }
    sort(&val[i][0],&val[i][sz[i]],cmp2);
}

long long minimum_walk(vector<int> pos, int s) {
    int i;

    assert(s==0);

    n = pos.size();
    for(i=0;i<n;i++) {
        if(i<pos[i]) p[0].push_back({i,pos[i]});
        if(i>pos[i]) p[1].push_back({pos[i],i});
    }

    for(i=0;i<2;i++) get(i);

    long long ans = 0;
    for(i=0;i<max(sz[0],sz[1]);i++) ans += max(val[0][i],val[1][i]);
    return ans*2;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30