oj.uz

Submission #926719

# Submission time Handle Problem Language Result Execution time Memory
926719 2024-02-13T14:33:56 Z denniskim Posters on the wall (CPSPC17_posters) C++17
90 / 100
 545 ms 231120 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> 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 3 ms 4356 KB Output is correct
2 Correct 3 ms 4356 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4356 KB Output is correct
2 Correct 3 ms 4356 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 29 ms 32368 KB Output is correct
5 Correct 28 ms 33796 KB Output is correct
6 Correct 23 ms 20488 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4356 KB Output is correct
2 Correct 3 ms 4356 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 29 ms 32368 KB Output is correct
5 Correct 28 ms 33796 KB Output is correct
6 Correct 23 ms 20488 KB Output is correct
7 Correct 237 ms 229248 KB Output is correct
8 Correct 515 ms 229232 KB Output is correct
9 Correct 312 ms 230356 KB Output is correct
10 Correct 480 ms 229768 KB Output is correct
11 Correct 413 ms 228896 KB Output is correct
12 Correct 391 ms 229852 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4356 KB Output is correct
2 Correct 3 ms 4356 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 29 ms 32368 KB Output is correct
5 Correct 28 ms 33796 KB Output is correct
6 Correct 23 ms 20488 KB Output is correct
7 Correct 271 ms 229384 KB Output is correct
8 Correct 522 ms 229844 KB Output is correct
9 Correct 312 ms 228568 KB Output is correct
10 Correct 493 ms 229336 KB Output is correct
11 Correct 355 ms 231120 KB Output is correct
12 Correct 359 ms 230360 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4356 KB Output is correct
2 Correct 3 ms 4356 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 29 ms 32368 KB Output is correct
5 Correct 28 ms 33796 KB Output is correct
6 Correct 23 ms 20488 KB Output is correct
7 Correct 237 ms 229248 KB Output is correct
8 Correct 515 ms 229232 KB Output is correct
9 Correct 312 ms 230356 KB Output is correct
10 Correct 480 ms 229768 KB Output is correct
11 Correct 413 ms 228896 KB Output is correct
12 Correct 391 ms 229852 KB Output is correct
13 Correct 271 ms 229384 KB Output is correct
14 Correct 522 ms 229844 KB Output is correct
15 Correct 312 ms 228568 KB Output is correct
16 Correct 493 ms 229336 KB Output is correct
17 Correct 355 ms 231120 KB Output is correct
18 Correct 359 ms 230360 KB Output is correct
19 Correct 289 ms 228600 KB Output is correct
20 Correct 545 ms 229004 KB Output is correct
21 Correct 307 ms 229584 KB Output is correct
22 Correct 470 ms 229088 KB Output is correct
23 Correct 377 ms 228820 KB Output is correct
24 Correct 380 ms 229352 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 229128 KB Output is correct
2 Correct 482 ms 229196 KB Output is correct
3 Correct 297 ms 229848 KB Output is correct
4 Correct 434 ms 230092 KB Output is correct
5 Correct 361 ms 230608 KB Output is correct
6 Correct 398 ms 229868 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 229128 KB Output is correct
2 Correct 482 ms 229196 KB Output is correct
3 Correct 297 ms 229848 KB Output is correct
4 Correct 434 ms 230092 KB Output is correct
5 Correct 361 ms 230608 KB Output is correct
6 Correct 398 ms 229868 KB Output is correct
7 Incorrect 356 ms 230104 KB Output isn't correct
8 Halted 0 ms 0 KB -