oj.uz

Submission #212415

# Submission time Handle Problem Language Result Execution time Memory
212415 2020-03-22T22:22:26 Z Benq Harvest (JOI20_harvest) C++14
100 / 100
 752 ms 120252 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 
 
#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
 
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
 
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
 
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
 
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
 
// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
	bool fst = 1; str res = "{";
	F0R(i,sz(v)) {
		if (!fst) res += ", ";
		fst = 0; res += ts(v[i]);
	}
	res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class T> str ts(T v) {
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }
 
// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif
 
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
/**
 * Description: A set (not multiset!) with support for finding the $n$'th
 * element, and finding the index of an element. Change \texttt{null\_type} for map.
 * Time: O(\log N)
 * Source: KACTL
 * Verification: many
 */
 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
	rb_tree_tag, tree_order_statistics_node_update>; 
#define ook order_of_key
#define fbo find_by_order
 
void treeExample() {
	Tree<int> t, t2; t.insert(8);
	auto it = t.insert(10).f; assert(it == t.lb(9));
	assert(t.ook(10) == 1 && t.ook(11) == 2 && *t.fbo(0) == 8);
	t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}
 
 
int N,M,L,C,A[MX],B[MX],par[MX], dis[MX];
vector<pair<ll,int>> query[MX];
ll ans[MX];
vi child[MX];
// int cyc[MX];
 
int dist(int a, int b) {
	int dif = C-(A[a]-A[b]);
	if (dif < 0) return A[a]-A[b];
	int need = cdiv(dif,L);
	return A[a]-A[b]+L*need;
	// A[a]-A[b]+L*? >= C
}
 
int cyclic(int a, int b) {
	if (a > b) a -= L;
	return b-a;
}
 
typedef pair<ll,Tree<pair<ll,int>>*> T;
int root,dumb;
T stor[MX];
bool vis[MX];
 
void ins(T& a, ll b) {
	a.s->insert({b-a.f,dumb++});
}
void merge(T& a, T& b) {
	if (a.s->size() < b.s->size()) swap(a,b);
	trav(t,*b.s) ins(a,t.f+b.f);
}
 
ll getAns(T& a, ll b) {
	return a.s->ook({b-a.f,MOD});
}
 
void dealCyc(int a) {
	vis[a] = 1;
	trav(t,child[a]) {
		if (t == root) continue;
		dealCyc(t);
		stor[t].f += dis[t];
		merge(stor[a],stor[t]);
	}
	if (a != root) trav(t,query[a]) {
		ans[t.s] += getAns(stor[a],t.f);
	}
}
 
ll quo(ll a, ll b) {
	if (a > 0 || a%b == 0) return a/b;
	return a/b-1;
}
 
ll rem(ll a, ll b) {
	ll r = a-quo(a,b)*b;
	assert(0 <= r && r < b);
	return r;
}
 
void finCyc() {
	ll d = dis[root];
	vi todo = {root};
	while (par[todo.bk] != root) {
		todo.pb(par[todo.bk]);
		d += dis[todo.bk];
	}
	dbg("FINCYC",root,stor[root].f,*stor[root].s);
	vector<pair<ll,int>> huh;
	F0R(i,sz(todo)) {
		int z = todo[i];
		trav(t,query[z]) huh.pb({t.f-stor[root].f,t.s});
		stor[root].f += dis[z]; // dbg(root,d,todo);
	}
	sort(all(huh));
	dbg(huh);
	vector<pair<ll,int>> toIns; 
	trav(t,*stor[root].s) toIns.pb(t);
	dbg(toIns);
	Tree<pair<ll,int>> cur;
	ll cnum = 0, csum = 0; int ind = 0;
	trav(t,huh) {
		while (ind < sz(toIns) && toIns[ind].f <= t.f) {
			cnum ++; csum += quo(toIns[ind].f,d);
			cur.insert({rem(toIns[ind].f,d),toIns[ind].s});
			ind ++;
		}
		ans[t.s] += cnum*quo(t.f,d)-csum;
		ans[t.s] += cur.ook({rem(t.f,d),MOD});
	}
}
 
int main() {
	setIO(); re(N,M,L,C);
	// assert(N <= 100000 && M <= 100000);
	FOR(i,1,N+1) stor[i].s = new Tree<pair<ll,int>>();
	FOR(i,1,N+1) re(A[i]);
	FOR(i,1,M+1) {
		re(B[i]);
		auto ind = lb(A+1,A+N+1,B[i])-A;
		if (ind == 1) ind = N+1;
		ind --; int d = cyclic(A[ind],B[i]);
		dbg(i,ind,d);
		ins(stor[ind],d);
	}
	int Q; re(Q);
	F0R(i,Q) {
		int V; ll T; re(V,T);
		query[V].pb({T,i});
	}
	FOR(i,1,N+1) {
		ll nex = (A[i]-C)%L; if (nex <= 0) nex += L;
		while (1) {
			int ind = ub(A+1,A+N+1,(int)nex)-A-1;
			if (ind == 0) { nex += L; continue; }
			par[i] = ind; child[ind].pb(i);
			dis[i] = dist(i,ind); break;
		}
		dbg(i,par[i],dis[i]);
	}
	FOR(i,1,N+1) if (!vis[i]) {
		int a = i, b = par[i];
		while (a != b) a = par[a], b = par[par[b]];
		root = a; dealCyc(a); 
		// if (N >= 10000) continue;
		finCyc();
	}
	F0R(i,Q) ps(ans[i]);
	// you should actually read the stuff at the bottom
}
 
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

Compilation message

harvest.cpp: In function 'void finCyc()':
harvest.cpp:227:47: warning: statement has no effect [-Wunused-value]
  dbg("FINCYC",root,stor[root].f,*stor[root].s);
                                               ^
harvest.cpp:235:10: warning: statement has no effect [-Wunused-value]
  dbg(huh);
          ^
harvest.cpp:238:12: warning: statement has no effect [-Wunused-value]
  dbg(toIns);
            ^
harvest.cpp: In function 'int main()':
harvest.cpp:262:15: warning: statement has no effect [-Wunused-value]
   dbg(i,ind,d);
               ^
harvest.cpp:278:23: warning: statement has no effect [-Wunused-value]
   dbg(i,par[i],dis[i]);
                       ^
harvest.cpp: In function 'void setIn(std::__cxx11::string)':
harvest.cpp:123:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
harvest.cpp: In function 'void setOut(std::__cxx11::string)':
harvest.cpp:124:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 14 ms 10624 KB Output is correct
3 Correct 15 ms 11008 KB Output is correct
4 Correct 15 ms 11136 KB Output is correct
5 Correct 14 ms 11136 KB Output is correct
6 Correct 14 ms 11136 KB Output is correct
7 Correct 15 ms 11136 KB Output is correct
8 Correct 14 ms 10752 KB Output is correct
9 Correct 13 ms 10880 KB Output is correct
10 Correct 14 ms 10880 KB Output is correct
11 Correct 14 ms 10880 KB Output is correct
12 Correct 17 ms 11136 KB Output is correct
13 Correct 16 ms 11264 KB Output is correct
14 Correct 16 ms 11096 KB Output is correct
15 Correct 14 ms 11136 KB Output is correct
16 Correct 14 ms 11136 KB Output is correct
17 Correct 15 ms 11136 KB Output is correct
18 Correct 15 ms 11008 KB Output is correct
19 Correct 14 ms 11008 KB Output is correct
20 Correct 14 ms 11008 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 19424 KB Output is correct
2 Correct 266 ms 49996 KB Output is correct
3 Correct 270 ms 51192 KB Output is correct
4 Correct 265 ms 53088 KB Output is correct
5 Correct 247 ms 67576 KB Output is correct
6 Correct 269 ms 67576 KB Output is correct
7 Correct 224 ms 45932 KB Output is correct
8 Correct 245 ms 46256 KB Output is correct
9 Correct 337 ms 71532 KB Output is correct
10 Correct 294 ms 72416 KB Output is correct
11 Correct 438 ms 71532 KB Output is correct
12 Correct 436 ms 71592 KB Output is correct
13 Correct 457 ms 71532 KB Output is correct
14 Correct 370 ms 72160 KB Output is correct
15 Correct 323 ms 63148 KB Output is correct
16 Correct 283 ms 59768 KB Output is correct
17 Correct 279 ms 59440 KB Output is correct
18 Correct 173 ms 27032 KB Output is correct
19 Correct 199 ms 26980 KB Output is correct
20 Correct 231 ms 49844 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 14 ms 10624 KB Output is correct
3 Correct 15 ms 11008 KB Output is correct
4 Correct 15 ms 11136 KB Output is correct
5 Correct 14 ms 11136 KB Output is correct
6 Correct 14 ms 11136 KB Output is correct
7 Correct 15 ms 11136 KB Output is correct
8 Correct 14 ms 10752 KB Output is correct
9 Correct 13 ms 10880 KB Output is correct
10 Correct 14 ms 10880 KB Output is correct
11 Correct 14 ms 10880 KB Output is correct
12 Correct 17 ms 11136 KB Output is correct
13 Correct 16 ms 11264 KB Output is correct
14 Correct 16 ms 11096 KB Output is correct
15 Correct 14 ms 11136 KB Output is correct
16 Correct 14 ms 11136 KB Output is correct
17 Correct 15 ms 11136 KB Output is correct
18 Correct 15 ms 11008 KB Output is correct
19 Correct 14 ms 11008 KB Output is correct
20 Correct 14 ms 11008 KB Output is correct
21 Correct 180 ms 19424 KB Output is correct
22 Correct 266 ms 49996 KB Output is correct
23 Correct 270 ms 51192 KB Output is correct
24 Correct 265 ms 53088 KB Output is correct
25 Correct 247 ms 67576 KB Output is correct
26 Correct 269 ms 67576 KB Output is correct
27 Correct 224 ms 45932 KB Output is correct
28 Correct 245 ms 46256 KB Output is correct
29 Correct 337 ms 71532 KB Output is correct
30 Correct 294 ms 72416 KB Output is correct
31 Correct 438 ms 71532 KB Output is correct
32 Correct 436 ms 71592 KB Output is correct
33 Correct 457 ms 71532 KB Output is correct
34 Correct 370 ms 72160 KB Output is correct
35 Correct 323 ms 63148 KB Output is correct
36 Correct 283 ms 59768 KB Output is correct
37 Correct 279 ms 59440 KB Output is correct
38 Correct 173 ms 27032 KB Output is correct
39 Correct 199 ms 26980 KB Output is correct
40 Correct 231 ms 49844 KB Output is correct
41 Correct 528 ms 110516 KB Output is correct
42 Correct 360 ms 64236 KB Output is correct
43 Correct 262 ms 53084 KB Output is correct
44 Correct 644 ms 80448 KB Output is correct
45 Correct 393 ms 96240 KB Output is correct
46 Correct 420 ms 96204 KB Output is correct
47 Correct 431 ms 96236 KB Output is correct
48 Correct 459 ms 96104 KB Output is correct
49 Correct 446 ms 96216 KB Output is correct
50 Correct 456 ms 75112 KB Output is correct
51 Correct 660 ms 86480 KB Output is correct
52 Correct 752 ms 111500 KB Output is correct
53 Correct 749 ms 111640 KB Output is correct
54 Correct 637 ms 111516 KB Output is correct
55 Correct 553 ms 102120 KB Output is correct
56 Correct 492 ms 106016 KB Output is correct
57 Correct 443 ms 94700 KB Output is correct
58 Correct 493 ms 106080 KB Output is correct
59 Correct 460 ms 94376 KB Output is correct
60 Correct 465 ms 94428 KB Output is correct
61 Correct 437 ms 94604 KB Output is correct
62 Correct 680 ms 94048 KB Output is correct
63 Correct 371 ms 67448 KB Output is correct
64 Correct 369 ms 67368 KB Output is correct
65 Correct 403 ms 67316 KB Output is correct
66 Correct 492 ms 65000 KB Output is correct
67 Correct 394 ms 54248 KB Output is correct
68 Correct 475 ms 64852 KB Output is correct
69 Correct 603 ms 119656 KB Output is correct
70 Correct 437 ms 105772 KB Output is correct
71 Correct 577 ms 120252 KB Output is correct
72 Correct 514 ms 116740 KB Output is correct