제출 #121499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121499		nvmdava	Shortcut (IOI16_shortcut)	C++17	0 / 100	4 ms	512 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>
using namespace std;
#define inf 10000000000000000LL
int n, c;
vector<long long> x, d;
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(x[q1] - d[q1] < x[q2] - d[q2]) return q1;
   return q2;
}
bool pos(long long len){
	long long bpmx, bpmn, bmmx, bmmn, pmx, pmn, mmx, mmn;
	bpmx = bmmx = mmn = pmn = inf;
	bpmn = bmmn = mmx = pmx = -inf;
	int mid = 0;
	int itm = 0, itp = 0, t = 0, r;
	for(itp = 1; itp < n; itp++){
		if(x[itp] + d[itp] - x[mid] + d[mid] > len){
			t = max(mid, t);
         if(t != itp - 1){
            r = get(t + 1, itp - 1);
            while(x[itp] + d[itp] - x[r] + d[r] > len){
               t = r;
               if(t == itp - 1) break;
               r = get(t + 1, itp - 1);
            }
         }
			while(itm <= t){
				mmx = max(mmx, x[itm] - d[itm]);
				mmn = min(mmx, x[itm] - d[itm]);
				pmx = max(pmx, x[itm] + d[itm]);
				pmn = min(pmn, x[itm] + d[itm]);
				itm++;
			}
		}
		if(itm){
         bpmx = min(bpmx, len - c + mmn + x[itp] - d[itp]);
         bpmn = max(bpmn, c - len + pmx + x[itp] + d[itp]);
         bmmx = min(bmmx, len - c - pmn + x[itp] - d[itp]);
         bmmn = max(bmmn, c - len - mmx + x[itp] + d[itp]);
		}
      if(x[itp] - d[itp] <= x[mid] - d[mid]) mid = itp;
	}
	if(bmmx < bmmn || bpmx < bpmn) return 0;
   int i, imn = 0, imx = 0;
   for(i = 0; i < n; i++){
      while(x[i] - x[imx] > bmmx) imx++;
      while(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 = 100000;
	::c = c;
	::n = n;
	for(auto& t : d){
		::d.push_back(t);
	}
	x.push_back(0);
	for(auto& t : le)
		x.push_back(x.back() + t);
	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(x[q1] - d[q1] < x[q2] - d[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: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3