oj.uz

답안 #1006411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006411 2024-06-24T01:45:05 Z AdamGS Bitaro, who Leaps through Time (JOI19_timeleap) C++17
30 / 100
 338 ms 74324 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item {
	ll t=0, a=0, b=0, c=0;
};
const ll INF=1e18+7;
const int LIM=3e5+7;
item tr[2][4*LIM];
int N=1;
item merge(item a, item b) {
	item x;
	x.c=a.c+b.c;
	if(a.t==0 && b.t==0) {
		x.a=max(a.a, b.a);
		x.b=min(a.b, b.b);
		if(x.a<=x.b) return x;
		if(a.a>b.b) {
			x.a=a.a;
			x.b=b.b;
			x.c+=a.a-b.b;
		} else {
			x.a=a.b;
			x.b=b.a;
		}
		x.t=1;
		return x;
	}
	x.t=1;
	if(b.t==0) {
		x.a=a.a;
		if(a.b>=b.b) {
			x.b=b.b;
			x.c+=a.b-b.b;
		} else if(a.b<=b.a) x.b=b.a;
		else x.b=a.b;
		return x;
	}
	x.b=b.b;
	if(a.t==0) {
		if(a.a>=b.a) {
			x.c+=a.a-b.a;
			x.a=a.a;
		} else if(a.b<=b.a) x.a=a.b;
		else x.a=b.a;
	} else {
		x.a=a.a;
		if(a.b>=b.a) x.c+=a.b-b.a;
	}
	return x;
}
void upd(int v, int k, item p) {
	v+=N;
	tr[k][v]=p;
	v/=2;
	while(v) {
		tr[k][v]=merge(tr[k][2*v], tr[k][2*v+1]);
		v/=2;
	}
}
item cnt(int l, int r, int k) {
	if(l>r) return {0, -INF, INF, 0};
	l+=N; r+=N;
	item ansl=tr[k][l];
	if(l==r) return ansl;
	item ansr=tr[k][r];
	while(l/2!=r/2) {
		if(l%2==0) ansl=merge(ansl, tr[k][l+1]);
		if(r%2==1) ansr=merge(tr[k][r-1], ansr);
		l/=2; r/=2;
	}
	return merge(ansl, ansr);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q;
	cin >> n >> q;
	while(N<n) N*=2;
	rep(i, n-1) {
		ll a, b;
		cin >> a >> b; --b;
		tr[0][N+i]={0, a-i, b-i, 0};
		tr[1][N+n-i-2]={0, a-(n-i-2), b-(n-i-2), 0};
	}
	for(int i=N-1; i; --i) {
		tr[0][i]=merge(tr[0][2*i], tr[0][2*i+1]);
		tr[1][i]=merge(tr[1][2*i], tr[1][2*i+1]);
	}
	while(q--) {
		int t;
		cin >> t;
		if(t==2) {
			ll a, b, c, d;
			cin >> a >> b >> c >> d; --a; --c;
			if(a<=c) {
				b-=a; d-=c;
				item x={1, b, b, 0}, y={1, d, d, 0};
				x=merge(x, cnt(a, c-1, 0));
				x=merge(x, y);
				cout << x.c << '\n';
				continue;
			}
			b-=(n-a-1); d-=(n-c-1);
			item x={1, b, b, 0}, y={1, d, d, 0};
			item xd=cnt(n-a-1, n-c-2, 1);
			x=merge(x, cnt(n-a-1, n-c-2, 1));
			x=merge(x, y);
			cout << x.c << '\n';
		}
	}
}

Compilation message

timeleap.cpp: In function 'int main()':
timeleap.cpp:111:9: warning: variable 'xd' set but not used [-Wunused-but-set-variable]
  111 |    item xd=cnt(n-a-1, n-c-2, 1);
      |         ^~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 321 ms 58196 KB Output is correct
2 Correct 331 ms 54868 KB Output is correct
3 Correct 304 ms 54932 KB Output is correct
4 Correct 302 ms 54752 KB Output is correct
5 Correct 306 ms 73592 KB Output is correct
6 Correct 336 ms 73812 KB Output is correct
7 Correct 319 ms 73688 KB Output is correct
8 Correct 335 ms 74324 KB Output is correct
9 Correct 302 ms 55092 KB Output is correct
10 Correct 324 ms 73784 KB Output is correct
11 Correct 328 ms 73804 KB Output is correct
12 Correct 320 ms 74068 KB Output is correct
13 Correct 338 ms 74324 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -