Submission #7101219


Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;

struct uf {
private:
	vector<int> par, ran;
public:
	uf(int n) {
		par.resize(n, 0);
		ran.resize(n, 0);
		rep(i, n) {
			par[i] = i;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (ran[x] < ran[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (ran[x] == ran[y])ran[x]++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

int ans[1 << 21];
int fakeans[1 << 21];
uf u(1 << 21);
void solve() {
	int n; cin >> n;
	vector<int> a(n);
	rep(i, n-1) {
		cin >> a[i];
	}
	int loc= 0;
	for (int i = n - 2; i >= 2;i--) {
		Rep(j, loc, loc + a[i]) {
			int to = 2 * (loc + a[i])-j;
			u.unite(j, to);
		}
		loc += a[i];
	}
	Rep(i, loc, (1 << 21)) {
		int memo = i - loc;
		int p = u.find(i);
		fakeans[p] = memo;
		ans[i] = memo;
	}
	rep(i, loc) {
		ans[i] = fakeans[u.find(i)];
	}
	int m; cin >> m;
	rep(i, m) {
		int x; cin >> x;
		int out;
		if (x >= loc) {
			out = x - loc;
		}
		else {
			out = ans[x];

		}
		cout << out + a[0] - a[1] << endl;
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(5);
	//init();
	solve();

	//cout << "finish" << endl;
	//stop
	return 0;
}

Submission Info

Submission Time
Task H - Tokaido
User heno239
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 2313 Byte
Status AC
Exec Time 372 ms
Memory 35328 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 700 / 700 900 / 900
Status
AC × 2
AC × 20
AC × 39
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 37 ms 31744 KB
01-02.txt AC 15 ms 33024 KB
01-03.txt AC 19 ms 30976 KB
01-04.txt AC 29 ms 31360 KB
01-05.txt AC 37 ms 31744 KB
01-06.txt AC 37 ms 31744 KB
01-07.txt AC 26 ms 31232 KB
01-08.txt AC 38 ms 31744 KB
01-09.txt AC 38 ms 31744 KB
01-10.txt AC 18 ms 31872 KB
01-11.txt AC 20 ms 30976 KB
01-12.txt AC 31 ms 30976 KB
01-13.txt AC 32 ms 32896 KB
01-14.txt AC 32 ms 31488 KB
01-15.txt AC 33 ms 31616 KB
01-16.txt AC 30 ms 31744 KB
01-17.txt AC 27 ms 33792 KB
01-18.txt AC 27 ms 33792 KB
01-19.txt AC 27 ms 33792 KB
02-01.txt AC 63 ms 31360 KB
02-02.txt AC 372 ms 33664 KB
02-03.txt AC 365 ms 32256 KB
02-04.txt AC 358 ms 32128 KB
02-05.txt AC 342 ms 31744 KB
02-06.txt AC 370 ms 32128 KB
02-07.txt AC 364 ms 32384 KB
02-08.txt AC 342 ms 31488 KB
02-09.txt AC 346 ms 33792 KB
02-10.txt AC 353 ms 32512 KB
02-11.txt AC 362 ms 32256 KB
02-12.txt AC 358 ms 32640 KB
02-13.txt AC 359 ms 32512 KB
02-14.txt AC 355 ms 33152 KB
02-15.txt AC 356 ms 35328 KB
02-16.txt AC 355 ms 35328 KB
sample-01.txt AC 15 ms 33024 KB
sample-02.txt AC 15 ms 33024 KB