oj.uz

Submission #926715

# Submission time Handle Problem Language Result Execution time Memory
926715 2024-02-13T14:32:26 Z denniskim Posters on the wall (CPSPC17_posters) C++17
90 / 100
 555 ms 230448 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);
	
	return gye.fi.fi * X * Y + gye.fi.se * X + gye.se.fi * Y + gye.se.se;
}

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 4356 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 4356 KB Output is correct
4 Correct 28 ms 32004 KB Output is correct
5 Correct 32 ms 32260 KB Output is correct
6 Correct 28 ms 21000 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 4356 KB Output is correct
4 Correct 28 ms 32004 KB Output is correct
5 Correct 32 ms 32260 KB Output is correct
6 Correct 28 ms 21000 KB Output is correct
7 Correct 237 ms 229684 KB Output is correct
8 Correct 525 ms 230448 KB Output is correct
9 Correct 316 ms 229076 KB Output is correct
10 Correct 464 ms 229824 KB Output is correct
11 Correct 392 ms 229796 KB Output is correct
12 Correct 378 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 4356 KB Output is correct
4 Correct 28 ms 32004 KB Output is correct
5 Correct 32 ms 32260 KB Output is correct
6 Correct 28 ms 21000 KB Output is correct
7 Correct 262 ms 228828 KB Output is correct
8 Correct 514 ms 230272 KB Output is correct
9 Correct 321 ms 228664 KB Output is correct
10 Correct 487 ms 229852 KB Output is correct
11 Correct 356 ms 228824 KB Output is correct
12 Correct 365 ms 230352 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 4356 KB Output is correct
4 Correct 28 ms 32004 KB Output is correct
5 Correct 32 ms 32260 KB Output is correct
6 Correct 28 ms 21000 KB Output is correct
7 Correct 237 ms 229684 KB Output is correct
8 Correct 525 ms 230448 KB Output is correct
9 Correct 316 ms 229076 KB Output is correct
10 Correct 464 ms 229824 KB Output is correct
11 Correct 392 ms 229796 KB Output is correct
12 Correct 378 ms 229852 KB Output is correct
13 Correct 262 ms 228828 KB Output is correct
14 Correct 514 ms 230272 KB Output is correct
15 Correct 321 ms 228664 KB Output is correct
16 Correct 487 ms 229852 KB Output is correct
17 Correct 356 ms 228824 KB Output is correct
18 Correct 365 ms 230352 KB Output is correct
19 Correct 286 ms 228808 KB Output is correct
20 Correct 555 ms 229408 KB Output is correct
21 Correct 304 ms 229332 KB Output is correct
22 Correct 486 ms 229896 KB Output is correct
23 Correct 380 ms 229452 KB Output is correct
24 Correct 381 ms 230100 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 228372 KB Output is correct
2 Correct 510 ms 229632 KB Output is correct
3 Correct 317 ms 229984 KB Output is correct
4 Correct 447 ms 228760 KB Output is correct
5 Correct 401 ms 229332 KB Output is correct
6 Correct 368 ms 230360 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 228372 KB Output is correct
2 Correct 510 ms 229632 KB Output is correct
3 Correct 317 ms 229984 KB Output is correct
4 Correct 447 ms 228760 KB Output is correct
5 Correct 401 ms 229332 KB Output is correct
6 Correct 368 ms 230360 KB Output is correct
7 Incorrect 366 ms 228820 KB Output isn't correct
8 Halted 0 ms 0 KB -