Submission #260481

#	Time	Username	Problem	Language	Result	Execution time	Memory
260481		patrikpavic2	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	0 / 100	479 ms	343904 KiB

timeleap

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int OFF = (1 << 19);
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 500;
const int LOG = 20;

pii T[2 * OFF][2];
int n, q;

inline pii mrg(pii A, pii B){
	return {max(A.X, B.X), min(A.Y, B.Y)};
}

void update(int i, int j, pii nw){
	T[i + OFF][j] = nw;
	for(i = (i + OFF) / 2 ; i ; i /= 2)
		T[i][j] = mrg(T[2 * i][j], T[2 * i + 1][j]);
}

int q_gr, q_x, q_j;

int desnoo(int i, int a, int b){
	//printf("i = %d a = %d b = %d q_gr = %d q_x = %d q_j = %d\n", i, a, b, q_gr, q_x, q_j);
	if(b < q_gr || (T[i][q_j].X <= q_x && q_x <= T[i][q_j].Y))
		return -1;
	if(a == b) return a;
	int L = desnoo(2 * i, a, (a + b) / 2);
	if(L != -1)
		return L;
	return desnoo(2 * i + 1, (a + b) / 2 + 1, b);
}

inline int desno(int gdje, int kol, int j){
	q_gr = gdje; q_x = kol; q_j = j;
	return desnoo(1, 0, OFF - 1);
}

int par[N][2][LOG], LL[N], RR[N], L[N][2], R[N][2];
ll cst[N][2][LOG];
int vis[N][2];

inline int get_pos(int x){
	if(x == 2 * n) return n;
	return x % n;
}

int main(){
	for(int i = 0;i < 2 * OFF;i++)
		T[i][0] = {-INF, INF}, T[i][1] = {-INF, INF};
	scanf("%d%d", &n, &q); n--;
	for(int i = 0;i < n;i++){
		scanf("%d%d", LL + i, RR + i); RR[i]--;
		L[i][0] = LL[i] - i, R[i][0] = RR[i] - i;
		L[n - i - 1][1] = LL[i] - (n - i - 1);
		R[n - i - 1][1] = RR[i] - (n - i - 1);
	}
	for(int k = 0;k < 2;k++){
		for(int i = 0;i < n;i++){
			update(i, k, {L[i][k], R[i][k]});
			vis[i][k] = L[i][k]; vis[i + n][k] = R[i][k];
		}
		update(n, k, {INF, -INF});
		for(int i = 0;i < 2 * n;i++){
			par[i][k][0] = desno(i % n, vis[i][k], k);
			if(par[i][k][0] == n){
				par[i][k][0] += n;
			}
			else if(vis[i][k] > R[par[i][k][0]][k]){
				cst[i][k][0] = vis[i][k] - R[par[i][k][0] % n][k];
				par[i][k][0] += n;
			}
			//printf("%d --> %d\n", i, par[i][k][0]);
		}	
		//printf("tu sam\n");
		par[2 * n][k][0] = 2 * n;
		for(int j = 1;j < LOG;j++){
			par[2 * n][k][j] = 2 * n;
			for(int i = 0;i < 2 * n;i++){
				par[i][k][j] = par[par[i][k][j - 1]][k][j - 1];
				cst[i][k][j] = cst[i][k][j - 1] + cst[par[i][k][j - 1]][k][j - 1];
			}
		}
		//printf("gotov precompute\n");
	}
	for(;q--;){
		int ty; scanf("%d", &ty);
		if(ty == 1) return 0;
		int st, en, v_st, v_en;
		scanf("%d%d%d%d", &st, &v_st, &en, &v_en); st--; en--;
		int k = (st > en);
		if(k){
			st = n - st; en = n - en;
		}
		v_st -= st; v_en -= en;
		//printf("st time = %d en time = %d\n", v_st, v_en);
		int cur = desno(st, v_st, k);
		//printf("vis %d\n", R[cur][k]);
		//printf("cur = %d\n", cur);
		if(cur >= en){
			printf("%lld\n", max((ll)v_st - v_en, 0LL));
			continue;
		}
		ll ans = 0;
		if(v_st > R[cur][k]){
			ans += v_st - R[cur][k];
			cur += n;
		}
		for(int i = LOG - 1;i >= 0;i--){
			if(get_pos(par[cur][k][i]) < en){	
				ans += cst[cur][k][i];
				cur = par[cur][k][i];
			}
		}
		//printf("cur = %d\n", cur);
		//printf("ans: %lld\n", ans);
		//printf("vis : %d krj : %d\n", vis[cur][k], v_en);
		ans += max((ll)vis[cur][k] - v_en, 0LL);
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q); n--;
  ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", LL + i, RR + i); RR[i]--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:98:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int ty; scanf("%d", &ty);
           ~~~~~^~~~~~~~~~~
timeleap.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &st, &v_st, &en, &v_en); st--; en--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66