Submission #263541

#	Time	Username	Problem	Language	Result	Execution time	Memory
263541		patrikpavic2	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	1167 ms	86408 KiB

timeleap

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

#define X first
#define Y second
#define PB push_back

using namespace std;

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

const int OFF = (1 << 19);
const int INF = 0x3f3f3f3f;

struct node{
	int f_t1, f_t2, c_t;
	int c_p, nula;
	ll f_p;
	node(){
		f_t1 = 0, f_t2 = INF, c_t = 0;
		c_p = INF, f_p = 0; nula = 0;
	}
	node(int s, int t){
		f_t1 = s + 1, f_t2 = t, c_t = s;
		f_p = 0, c_p = t - 1; nula = 0;
	}
	int get_time(int s_t){
		return min(f_t2, f_t1 + max(0, s_t - c_t));
	}
	ll get_price(int s_t){
		return f_p + max(s_t - c_p, 0);
	}
	void print(){
		printf("-	-	-\n");
		printf("f_t1 = %d  f_t2 = %d\n", f_t1, f_t2);
		printf("c_t = %d\n", c_t);
		printf("f_p = %lld c_p = %d\n", f_p, c_p);
		printf("nula = %d\n", nula);
	}
};

node NULA, T[2 * OFF][2];

node operator+(node A, node B){
	if(A.nula) return B;
	if(B.nula) return A;
	node C;
	C.f_t1 = B.get_time(A.f_t1);
	C.f_t2 = B.get_time(A.f_t2);
	C.c_t = A.c_t;
	if(A.f_t1 < B.c_t){
		if(A.f_t2 >= B.c_t)
			C.c_t += B.c_t - A.f_t1;
		else
			C.c_t = INF;
	}
	C.c_p = A.c_p;
	C.f_p = A.f_p + B.get_price(A.f_t1);
	if(A.get_time(A.c_p) > B.c_p && A.f_t1 <= B.c_p){
		C.c_p = A.c_p - (A.get_time(A.c_p) - B.c_p);
	}
	if(A.f_t1 > B.c_p)
		C.c_p = min(C.c_p, A.c_t);
	return C;
}

node query(int i, int a, int b, int lo, int hi, bool rev){
	if(lo <= a && b <= hi) return T[i][rev];
	if(a > hi || b < lo) return NULA; 
	if(!rev)
		return query(2 * i, a, (a + b) / 2, lo, hi, rev) + query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, rev);
	else
		return query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, rev) + query(2 * i, a, (a + b) / 2, lo, hi, rev);
}

void update(int i, int s, int t){
	T[OFF + i][0] = node(s, t);
	T[OFF + i][1] = node(s, t);
	for(i = (OFF + i) / 2 ; i ; i /= 2){
		T[i][0] = T[2 * i][0] + T[2 * i + 1][0];
		T[i][1] = T[2 * i + 1][1] + T[2 * i][1];
	}
}

int n, q;

int main(){
	NULA.nula = 1;
	for(int i = 0;i < 2 * OFF;i++) 
		T[i][0] = NULA, T[i][1] = NULA;
	scanf("%d%d", &n, &q);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		update(i, x, y);
	}
	for(int i = 0;i < q;i++){
		int ty; scanf("%d", &ty);
		if(ty == 1){
			int p, x, y; scanf("%d%d%d", &p, &x, &y);
			update(p, x, y);
		}
		else{
			int l, l_t, r, r_t; scanf("%d%d%d%d", &l,&l_t, &r, &r_t);
			node ret = NULA;
			if(l < r)
				ret = query(1, 0, OFF - 1, l, r - 1, 0);
			if(l > r)
				ret = query(1, 0, OFF - 1, r, l - 1, 1);
			//ret.print();
			ll ans = ret.get_price(l_t) + max(0, ret.get_time(l_t) - r_t);
			printf("%lld\n", ans);
		}
	}
	return 0;
}

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:95:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:99:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
timeleap.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |    int p, x, y; scanf("%d%d%d", &p, &x, &y);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:105:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |    int l, l_t, r, r_t; scanf("%d%d%d%d", &l,&l_t, &r, &r_t);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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