oj.uz

Submission #926721

# Submission time Handle Problem Language Result Execution time Memory
926721 2024-02-13T14:35:21 Z denniskim Posters on the wall (CPSPC17_posters) C++17
90 / 100
 680 ms 360384 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<lll, lll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct gujo
{
	ll X, Y, A, B, C, D;
	
	bool operator < (const gujo &xx) const
	{
		return X < xx.X;
	}
};

ll r, c, n, q, m;
vector<gujo> upd;
vector<ll> zip;
ll all, bll, cll, dll, ell;
ll LL;
ll rt[5000010];
ll x[5000010];
ll cc;
ll siz;

struct node
{
	ll L, R;
	pair<pll, pll> gap;
};

struct persistentsegtree
{
	vector<node> seg;
	
	void new_node(void)
	{
		seg.push_back({-1, -1, {{0, 0}, {0, 0}}});
	}
	
	void init(ll no, ll s, ll e)
	{
		if(s == e)
			return;
		
		seg[no].L = (ll)seg.size();
		new_node();
		seg[no].R = (ll)seg.size();
		new_node();
		
		init(seg[no].L, s, (s + e) >> 1);
		init(seg[no].R, ((s + e) >> 1) + 1, e);
	}
	
	void update(ll no, ll last, ll s, ll e, ll w, pair<pll, pll> v)
	{
		if(e < w || w < s)
			return;
		
		if(s == e)
		{
			seg[no].gap.fi.fi = seg[last].gap.fi.fi + v.fi.fi;
			seg[no].gap.fi.se = seg[last].gap.fi.se + v.fi.se;
			seg[no].gap.se.fi = seg[last].gap.se.fi + v.se.fi;
			seg[no].gap.se.se = seg[last].gap.se.se + v.se.se;
			
			return;
		}
		
		ll mid = (s + e) >> 1;
		
		if(s <= w && w <= mid)
		{
			if(seg[no].L == -1)
			{
				seg[no].L = (ll)seg.size();
				new_node();
			}
			
			seg[no].R = seg[last].R;
			update(seg[no].L, seg[last].L, s, mid, w, v);
		}
		
		else
		{
			if(seg[no].R == -1)
			{
				seg[no].R = (ll)seg.size();
				new_node();
			}
			
			seg[no].L = seg[last].L;
			update(seg[no].R, seg[last].R, mid + 1, e, w, v);
		}
		
		seg[no].gap.fi.fi = seg[seg[no].L].gap.fi.fi;
		seg[no].gap.fi.se = seg[seg[no].L].gap.fi.se;
		seg[no].gap.se.fi = seg[seg[no].L].gap.se.fi;
		seg[no].gap.se.se = seg[seg[no].L].gap.se.se;
		
		seg[no].gap.fi.fi += seg[seg[no].R].gap.fi.fi;
		seg[no].gap.fi.se += seg[seg[no].R].gap.fi.se;
		seg[no].gap.se.fi += seg[seg[no].R].gap.se.fi;
		seg[no].gap.se.se += seg[seg[no].R].gap.se.se;
	}
	
	pair<pll, pll> query(ll no, ll s, ll e, ll l, ll r)
	{
		if(e < l || r < s || l > r)
			return {{0, 0}, {0, 0}};
		
		if(l <= s && e <= r)
			return seg[no].gap;
		
		pair<pll, pll> ret;
		
		ret = {{0, 0}, {0, 0}};
		
		if(seg[no].L != -1)
		{
			pair<pll, pll> tmp = query(seg[no].L, s, (s + e) >> 1, l, r);
			
			ret.fi.fi += tmp.fi.fi;
			ret.fi.se += tmp.fi.se;
			ret.se.fi += tmp.se.fi;
			ret.se.se += tmp.se.se;
		}
		
		if(seg[no].R != -1)
		{
			pair<pll, pll> tmp = query(seg[no].R, ((s + e) >> 1) + 1, e, l, r);
			
			ret.fi.fi += tmp.fi.fi;
			ret.fi.se += tmp.fi.se;
			ret.se.fi += tmp.se.fi;
			ret.se.se += tmp.se.se;
		}
		
		return ret;
	}
}segt;

void update(ll W, ll A, ll B, ll C, ll D)
{
	segt.update(rt[cc], rt[cc - 1], 1, siz, W, {{A * C, A * D}, {B * C, B * D}});
}

ll num(ll X)
{
	return lower_bound(zip.begin(), zip.end(), X) - zip.begin() + 1;
}

ll query(ll X, ll Y)
{
	ll real_X = 0;
	ll real_Y = upper_bound(zip.begin(), zip.end(), Y) - zip.begin();
	
	ll l = 0, r = cc;
	
	while(l <= r)
	{
		ll mid = (l + r) >> 1;
		
		if(x[mid] <= X)
			l = mid + 1;
		else
			r = mid - 1;
	}
	
	real_X = r;
	
	if(real_X <= 0)
		return 0;
	
	pair<pll, pll> gye = segt.query(rt[real_X], 1, siz, 1, real_Y);
	lll ret = (lll)gye.fi.fi * X * Y + (lll)gye.fi.se * X + (lll)gye.se.fi * Y + (lll)gye.se.se;
	
	return (ll)ret;
}

int main(void)
{
	fastio
	
	cin >> r >> c >> n >> q >> m;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		cin >> all >> cll >> bll >> dll;
		
		if(all > bll)
			swap(all, bll);
		
		if(cll > dll)
			swap(cll, dll);
		
		all++, cll++;
		
		zip.push_back(all);
		zip.push_back(bll);
		zip.push_back(cll);
		zip.push_back(dll);
		upd.push_back({all, cll, 1, -(all - 1), 1, -(cll - 1)});
		upd.push_back({all, dll, 1, -(all - 1), -1, dll});
		upd.push_back({bll, cll, -1, bll, 1, -(cll - 1)});
		upd.push_back({bll, dll, 1, -bll, 1, -dll});
	}
	
	zip.push_back(-1);
	compress(zip);
	sort(upd.begin(), upd.end());
	
	siz = (ll)zip.size();
	segt.new_node();
	segt.init(0, 1, siz);
	x[0] = 0, rt[0] = 0;
	
	for(ll i = 0 ; i < (ll)upd.size() ; i++)
	{
		cc++;
		x[cc] = upd[i].X;
		rt[cc] = (ll)segt.seg.size();
		segt.new_node();
		
		update(num(upd[i].Y), upd[i].A, upd[i].B, upd[i].C, upd[i].D);
	}
	
	while(q--)
	{
		cin >> all >> cll >> bll >> dll >> ell;
		
		all = (all + LL * ell % m) % m;
		bll = (bll + LL * ell % m) % m;
		cll = (cll + LL * ell % m) % m;
		dll = (dll + LL * ell % m) % m;
		
		if(all > bll)
			swap(all, bll);
		
		if(cll > dll)
			swap(cll, dll);
		
		all++, cll++;
		
		LL = query(bll, dll) - query(bll, cll - 1) - query(all - 1, dll) + query(all - 1, cll - 1);
		cout << LL en;
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5356 KB Output is correct
2 Correct 4 ms 5360 KB Output is correct
3 Correct 4 ms 5360 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5356 KB Output is correct
2 Correct 4 ms 5360 KB Output is correct
3 Correct 4 ms 5360 KB Output is correct
4 Correct 39 ms 49920 KB Output is correct
5 Correct 46 ms 49668 KB Output is correct
6 Correct 41 ms 29444 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5356 KB Output is correct
2 Correct 4 ms 5360 KB Output is correct
3 Correct 4 ms 5360 KB Output is correct
4 Correct 39 ms 49920 KB Output is correct
5 Correct 46 ms 49668 KB Output is correct
6 Correct 41 ms 29444 KB Output is correct
7 Correct 356 ms 358604 KB Output is correct
8 Correct 680 ms 360384 KB Output is correct
9 Correct 403 ms 358840 KB Output is correct
10 Correct 587 ms 358564 KB Output is correct
11 Correct 480 ms 359884 KB Output is correct
12 Correct 510 ms 358772 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5356 KB Output is correct
2 Correct 4 ms 5360 KB Output is correct
3 Correct 4 ms 5360 KB Output is correct
4 Correct 39 ms 49920 KB Output is correct
5 Correct 46 ms 49668 KB Output is correct
6 Correct 41 ms 29444 KB Output is correct
7 Correct 363 ms 358920 KB Output is correct
8 Correct 672 ms 359004 KB Output is correct
9 Correct 432 ms 359312 KB Output is correct
10 Correct 547 ms 359888 KB Output is correct
11 Correct 468 ms 359508 KB Output is correct
12 Correct 448 ms 359368 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5356 KB Output is correct
2 Correct 4 ms 5360 KB Output is correct
3 Correct 4 ms 5360 KB Output is correct
4 Correct 39 ms 49920 KB Output is correct
5 Correct 46 ms 49668 KB Output is correct
6 Correct 41 ms 29444 KB Output is correct
7 Correct 356 ms 358604 KB Output is correct
8 Correct 680 ms 360384 KB Output is correct
9 Correct 403 ms 358840 KB Output is correct
10 Correct 587 ms 358564 KB Output is correct
11 Correct 480 ms 359884 KB Output is correct
12 Correct 510 ms 358772 KB Output is correct
13 Correct 363 ms 358920 KB Output is correct
14 Correct 672 ms 359004 KB Output is correct
15 Correct 432 ms 359312 KB Output is correct
16 Correct 547 ms 359888 KB Output is correct
17 Correct 468 ms 359508 KB Output is correct
18 Correct 448 ms 359368 KB Output is correct
19 Correct 397 ms 358340 KB Output is correct
20 Correct 656 ms 359036 KB Output is correct
21 Correct 377 ms 359372 KB Output is correct
22 Correct 616 ms 359628 KB Output is correct
23 Correct 482 ms 359876 KB Output is correct
24 Correct 487 ms 359628 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 359364 KB Output is correct
2 Correct 601 ms 358408 KB Output is correct
3 Correct 383 ms 359376 KB Output is correct
4 Correct 532 ms 358700 KB Output is correct
5 Correct 441 ms 358376 KB Output is correct
6 Correct 454 ms 359628 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 359364 KB Output is correct
2 Correct 601 ms 358408 KB Output is correct
3 Correct 383 ms 359376 KB Output is correct
4 Correct 532 ms 358700 KB Output is correct
5 Correct 441 ms 358376 KB Output is correct
6 Correct 454 ms 359628 KB Output is correct
7 Incorrect 464 ms 358848 KB Output isn't correct
8 Halted 0 ms 0 KB -