oj.uz

Submission #926724

# Submission time Handle Problem Language Result Execution time Memory
926724 2024-02-13T14:39:14 Z denniskim Posters on the wall (CPSPC17_posters) C++17
100 / 100
 741 ms 384752 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
{
	lll 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<lll> zip;
ll all, bll, cll, dll, ell;
lll LL;
lll rt[5000010];
lll 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(lll no, lll s, lll 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(lll no, lll last, lll s, lll e, lll 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;
		}
		
		lll 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(lll no, lll s, lll e, lll l, lll 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(lll W, lll A, lll B, lll C, lll D)
{
	segt.update(rt[cc], rt[cc - 1], 1, siz, W, {{A * C, A * D}, {B * C, B * D}});
}

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

lll query(lll X, lll Y)
{
	lll real_X = 0;
	lll real_Y = upper_bound(zip.begin(), zip.end(), Y) - zip.begin();
	
	lll 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 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)LL en;
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6624 KB Output is correct
2 Correct 4 ms 5348 KB Output is correct
3 Correct 4 ms 5348 KB Output is correct
4 Correct 40 ms 50944 KB Output is correct
5 Correct 46 ms 53504 KB Output is correct
6 Correct 34 ms 31212 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6624 KB Output is correct
2 Correct 4 ms 5348 KB Output is correct
3 Correct 4 ms 5348 KB Output is correct
4 Correct 40 ms 50944 KB Output is correct
5 Correct 46 ms 53504 KB Output is correct
6 Correct 34 ms 31212 KB Output is correct
7 Correct 388 ms 380612 KB Output is correct
8 Correct 723 ms 380380 KB Output is correct
9 Correct 445 ms 379432 KB Output is correct
10 Correct 656 ms 379620 KB Output is correct
11 Correct 519 ms 379076 KB Output is correct
12 Correct 530 ms 379844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6624 KB Output is correct
2 Correct 4 ms 5348 KB Output is correct
3 Correct 4 ms 5348 KB Output is correct
4 Correct 40 ms 50944 KB Output is correct
5 Correct 46 ms 53504 KB Output is correct
6 Correct 34 ms 31212 KB Output is correct
7 Correct 394 ms 377544 KB Output is correct
8 Correct 672 ms 379084 KB Output is correct
9 Correct 474 ms 380960 KB Output is correct
10 Correct 618 ms 381320 KB Output is correct
11 Correct 508 ms 377408 KB Output is correct
12 Correct 530 ms 380888 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6624 KB Output is correct
2 Correct 4 ms 5348 KB Output is correct
3 Correct 4 ms 5348 KB Output is correct
4 Correct 40 ms 50944 KB Output is correct
5 Correct 46 ms 53504 KB Output is correct
6 Correct 34 ms 31212 KB Output is correct
7 Correct 388 ms 380612 KB Output is correct
8 Correct 723 ms 380380 KB Output is correct
9 Correct 445 ms 379432 KB Output is correct
10 Correct 656 ms 379620 KB Output is correct
11 Correct 519 ms 379076 KB Output is correct
12 Correct 530 ms 379844 KB Output is correct
13 Correct 394 ms 377544 KB Output is correct
14 Correct 672 ms 379084 KB Output is correct
15 Correct 474 ms 380960 KB Output is correct
16 Correct 618 ms 381320 KB Output is correct
17 Correct 508 ms 377408 KB Output is correct
18 Correct 530 ms 380888 KB Output is correct
19 Correct 428 ms 380608 KB Output is correct
20 Correct 729 ms 380920 KB Output is correct
21 Correct 467 ms 379016 KB Output is correct
22 Correct 657 ms 379592 KB Output is correct
23 Correct 549 ms 379076 KB Output is correct
24 Correct 567 ms 379164 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 383176 KB Output is correct
2 Correct 671 ms 380916 KB Output is correct
3 Correct 442 ms 377544 KB Output is correct
4 Correct 607 ms 380376 KB Output is correct
5 Correct 515 ms 380616 KB Output is correct
6 Correct 555 ms 381088 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 383176 KB Output is correct
2 Correct 671 ms 380916 KB Output is correct
3 Correct 442 ms 377544 KB Output is correct
4 Correct 607 ms 380376 KB Output is correct
5 Correct 515 ms 380616 KB Output is correct
6 Correct 555 ms 381088 KB Output is correct
7 Correct 423 ms 379844 KB Output is correct
8 Correct 741 ms 384168 KB Output is correct
9 Correct 459 ms 381184 KB Output is correct
10 Correct 710 ms 384752 KB Output is correct
11 Correct 533 ms 381636 KB Output is correct
12 Correct 537 ms 382792 KB Output is correct