Submission #121724

#	Time	Username	Problem	Language	Result	Execution time	Memory
121724		nvmdava	Shortcut (IOI16_shortcut)	C++17	100 / 100	1782 ms	127736 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 10000000000000000LL
int n, c;
vector<long long> xpd, xmd;
vector<long long> x;
int sp[1000005][20];
int lg[1000005];

int get(int l, int r){
   int sz = lg[r - l + 1];
   int q2 = sp[r][sz];
   int q1 = sp[l + (1 << sz) - 1][sz];
   if(xmd[q1] < xmd[q2]) return q1;
   return q2;
}
bool pos(long long len){
	long long bpmx, bpmn, bmmx, bmmn, pmx, mmn, f = len - c;
	bpmx = bmmx = mmn = inf;
	bpmn = bmmn = pmx = -inf;
	int mid = 0;
	int itm = 0, itp = 0, t = 0, r;
   for(itp = 1; itp < n; itp++){
		if(xpd[itp] - xmd[mid] > len) break;
      if(xmd[itp] <= xmd[mid]) mid = itp;
   }
 
   t = mid;
	for(;itp < n; itp++){
      if(t != itp - 1){
         r = get(t + 1, itp - 1);
         while(xpd[itp] - xmd[r] > len){
            t = r;
            if(t == itp - 1) break;
            r = get(t + 1, itp - 1);
         }
      }
      while(itm <= t){
         mmn = min(mmn, xmd[itm]);
         pmx = max(pmx, xpd[itm]);
         itm++;
      }
      bpmx = min(bpmx, f + mmn + xmd[itp]);
      bpmn = max(bpmn, -f + pmx + xpd[itp]);
      bmmx = min(bmmx, f - pmx + xmd[itp]);
      bmmn = max(bmmn, -f - mmn + xpd[itp]);
		if(bmmx < bmmn || bpmx < bpmn) return 0;
	}
   int i, imn = 0, imx = 0;
   for(i = 0; i < n; i++){
      while(imx < n && x[i] - x[imx] > bmmx) imx++;
      while(imn < n && x[i] - x[imn] >= bmmn) imn++;
      if(imn > imx){
         if(x[i] + x[imn - 1] <= bpmx && x[i] + x[imn - 1] >= bpmx) return 1;
         if(x[i] + x[imx] <= bpmx && x[i] + x[imx] >= bpmx) return 1;
      }
   }
   imn = n - 1;
   imx = n - 1;
   for(i = 0; i < n; i++){
      while(imx >= 0 && x[i] + x[imx] > bpmx) imx--;
      while(imn >= 0 && x[i] + x[imn] >= bpmn) imn--;
      if(i > imx) return 0;
      if(imn < imx){
         if(x[imx] - x[i] <= bmmx && x[imx] - x[i] >= bmmn) return 1;
         if(x[imn + 1] - x[i] <= bmmx && x[imn + 1] - x[i] >= bmmn) return 1;
      }
   }
   return 0;
}
 
long long find_shortcut(int n, vector<int> le, vector<int> d, int c){
	long long m, l = 0, r;
	::c = c;
	::n = n;
	x.push_back(0);
	for(auto& t : le){
		x.push_back(x.back() + t);
	}
   for(int i = 0; i < n; i++){
      xpd.push_back(x[i] + d[i]);
      xmd.push_back(x[i] - d[i]);
   }
   r = x[n - 1] + 2000000000;
	for(int i = 0; i < n; i++){
      sp[i][0] = i;
      for(int j = 1; j < 20; j++){
         if((1 << j) > i) break;
         int q1, q2;
         q1 = sp[i][j - 1];
         q2 = sp[i - (1 << (j - 1))][j - 1];
         if(xmd[q1] < xmd[q2])
            sp[i][j] = q1;
         else sp[i][j] = q2;
      }
	}
 
	for(int i = 2; i < n; i++){
      lg[i] = lg[i >> 1] + 1;
	}
 
	while(l != r){
		m = (l + r) >> 1;
		if(pos(m)) r = m;
		else l = m + 1;
	}
   return l;
}

• 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