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 |
|
|
|
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 |