Submission #545024

#	Time	Username	Problem	Language	Result	Execution time	Memory
545024		Bobby	Shortcut (IOI16_shortcut)	C++17	100 / 100	1130 ms	72928 KiB

shortcut

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define sc second

const int maxN = 1000 * 1000;
const long long inf = (long long) 1e18;

long long x[maxN + 1];
long long d[maxN + 1];
bool important[maxN + 1];
long long maxsump[maxN + 1], mindifp[maxN + 1];

long long difl, difr, suml, sumr;
double checkempty = 0.0;

bool isNonempty(int n) {    
    if (suml > sumr || difl > difr)	
    	return false;
	
    int p = 0;
	for (int i = 1; i < n; i++) {
		while (p < i && x[p] + x[i] <= sumr && x[p] - x[i] <= difr)
			p++;
		while (p > 0 && (x[p] + x[i] > sumr || x[p] - x[i] > difr))
			p--;
    
		if (x[i] + x[p] >= suml && x[i] + x[p] <= sumr && x[p] - x[i] >= difl && x[p] - x[i] <= difr) {
			return true;
		}
	}

	return false;
}

bool check(int n, int c, long long k) {
    suml = difl = -inf;
    sumr = difr = inf;

    int p = -1;
    deque <int> q;

    for (int i = 0; i < n; i++) {
        if (important[i]) {
            if (q.front() == p)
                q.pop_front();
                
            while (p + 1 < i && d[q.front()] - x[q.front()] > k - x[i] - d[i]) {
                p++;
                if (q.front() == p)
                    q.pop_front();            
            }

//            cerr << i << ' ' << p << ' ' << x[i] << ' ' << d[i] << ' ' << k << ' ' << c << ' ' << maxsump[p] << endl;

            if (p != -1) {
                suml = max(suml, x[i] + d[i] - k + c + maxsump[p]);
                sumr = min(sumr, x[i] - d[i] + k - c + mindifp[p]);
                difl = max(difl, -x[i] + d[i] - k + c + maxsump[p]);         
                difr = min(difr, -x[i] - d[i] + k - c  + mindifp[p]);    
            }
        }     
        while (!q.empty() && d[q.back()] - x[q.back()] <= d[i] - x[i])
            q.pop_back();
        q.push_back(i);
    }

//    cerr << k << ' ' << suml << ' ' << sumr << ' ' << difl << ' ' << difr << endl;

    return isNonempty(n);
}

long long find_shortcut(int n, vector <int> len, vector <int> dep, int c) {
    x[0] = 0ll;

    for (int i = 0; i < n; i++) {
        d[i] = dep[i];
        if (i + 1 < n) {
            x[i + 1] = x[i] + len[i];
        }    
    }

    maxsump[0] = d[0];
    mindifp[0] = -d[0];
    
    for (int i = 1; i < n; i++) {
        maxsump[i] = max(maxsump[i - 1], x[i] + d[i]);
        mindifp[i] = min(mindifp[i - 1], x[i] - d[i]);
    }

    important[n - 1] = true;
    int curb = n - 1;
    for (int i = n - 2; i >= 0; i--) {
        if (x[i] - d[i] < x[curb] - d[curb]) {
            important[i] = true;
            curb = i;    
        }
    }

    long long lb = 0ll;
    long long rb = x[n - 1] + 2e9;
    while (lb < rb) {
    	long long mid = (lb + rb) / 2;
    	if (check(n, c, mid))
    		rb = mid;
    	else
    		lb = mid + 1;
    }

    return lb;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 3 / 3