oj.uz

답안 #743504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743504 2023-05-17T12:50:55 Z myrcella Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 340 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "shortcut.h"

const int maxn = 3e3+10;

ll pos[maxn];
ll a[maxn];
int n;
ll C;
ll tree[2][maxn*maxn*4],add[maxn*maxn*4];
set <ll> p;
vector <pii> tmp;

void init (int c,int cl,int cr,ll d) {
	add[c] = 0;
	if (cl==cr) {
		int l = tmp[cl].fi, r = tmp[cl].se;
		tree[0][c] = pos[r]-(d-pos[l]-a[l]-a[r]);
		tree[1][c] = pos[r]+(d-pos[l]-a[l]-a[r]);
//		debug(pos[r]);
//		debug(pos[l]);
//		debug(tree[0][c]),debug(tree[1][c]);
	}
	else {
		int mid=cl+cr>>1;
		init(c<<1,cl,mid,d);
		init(c<<1|1,mid+1,cr,d);
		tree[0][c] = max(tree[0][c<<1],tree[0][c<<1|1]);
		tree[1][c] = min(tree[1][c<<1],tree[1][c<<1|1]);
	}
}

void update(int c,int cl,int cr,int l,int r,ll val) {
	if (l>r) return;
	if (l<=cl and cr<=r) {
		tree[0][c] -= val;
		tree[1][c] += val;
		add[c]+=val;
//		debug(val);
//		cout<<cl<<" "<<tree[0][c]<<" "<<tree[1][c]<<endl;
		return;
	}
	if (add[c]!=0) {
		tree[0][c<<1] -= add[c];
		tree[0][c<<1|1] -= add[c];
		tree[1][c<<1] += add[c];
		tree[1][c<<1|1] += add[c];
		add[c<<1] += add[c];
		add[c<<1|1] += add[c];
		add[c] = 0;
	}
	int mid=cl+cr>>1;
	if (l<=mid) update(c<<1,cl,mid,l,r,val);
	if (r>mid) update(c<<1|1,mid+1,cr,l,r,val);
	tree[0][c] = max(tree[0][c<<1],tree[0][c<<1|1]);
	tree[1][c] = min(tree[1][c<<1],tree[1][c<<1|1]);
}

bool check(ll d) {
	tmp.clear();
	rep(i,0,n) 
		rep(j,i+1,n) {
			if (pos[j]-pos[i]+a[i]+a[j]>d) {
				if (d<C) return false;
				tmp.pb({i,j});
			}
		}
	if (tmp.empty()) return true;
//	debug(d),debug(SZ(tmp));
//	for (auto it:tmp) debug(it.fi),debug(it.se);
	d -= C;
	init(1,0,SZ(tmp)-1,d);
	if (tree[0][1]<=tree[1][1]) return true;
	int cur = 0;
	rep(i,1,n) {
		while (cur<SZ(tmp) and tmp[cur].fi<i) cur++;
		update(1,0,SZ(tmp)-1,0,cur-1,-pos[i]+pos[i-1]);
		update(1,0,SZ(tmp)-1,cur,SZ(tmp)-1,pos[i]-pos[i-1]);
		if (tree[0][1]<=tree[1][1]) return true;
	}
	return false;
}

long long find_shortcut(int N, std::vector<int> L, std::vector<int> d, int c)
{
	p.clear();
	n = N; C=c;
	pos[0] = 0;
	p.insert(0);
	rep(i,1,n) pos[i] = pos[i-1] + L[i-1],p.insert(pos[i]);
	rep(i,0,n) a[i] = d[i];
	ll l = 0,r = 1e16;
	while (l<r) {
		ll mid = (l+r)/2;
		if (check(mid)) r = mid;
		else l = mid+1;
	}
    return l;
}

Compilation message

shortcut.cpp: In function 'void init(int, int, int, long long int)':
shortcut.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid=cl+cr>>1;
      |           ~~^~~
shortcut.cpp: In function 'void update(int, int, int, int, int, long long int)':
shortcut.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |  int mid=cl+cr>>1;
      |          ~~^~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 KB n = 4, 80 is a correct answer
2 Correct 1 ms 304 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 308 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 340 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 1 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 308 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 280 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -