oj.uz

Submission #926705

# Submission time Handle Problem Language Result Execution time Memory
926705 2024-02-13T14:28:49 Z denniskim Posters on the wall (CPSPC17_posters) C++17
90 / 100
 543 ms 232568 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[2000010];
ll x[2000010];
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;
	}
	
	ll query(ll no, ll s, ll e, ll l, ll r, ll X, ll Y)
	{
		if(e < l || r < s || l > r)
			return 0;
		
		if(l <= s && e <= r)
			return seg[no].gap.fi.fi * X * Y + seg[no].gap.fi.se * X + seg[no].gap.se.fi * Y + seg[no].gap.se.se;
		
		ll ret = 0;
		
		if(seg[no].L != -1)
			ret += query(seg[no].L, s, (s + e) >> 1, l, r, X, Y);
		
		if(seg[no].R != -1)
			ret += query(seg[no].R, ((s + e) >> 1) + 1, e, l, r, X, Y);
		
		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;
	
	return segt.query(rt[real_X], 1, siz, 1, real_Y, X, Y);
}

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 2 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 2 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 31 ms 30556 KB Output is correct
5 Correct 27 ms 31736 KB Output is correct
6 Correct 20 ms 18440 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 31 ms 30556 KB Output is correct
5 Correct 27 ms 31736 KB Output is correct
6 Correct 20 ms 18440 KB Output is correct
7 Correct 255 ms 227928 KB Output is correct
8 Correct 477 ms 228820 KB Output is correct
9 Correct 296 ms 231640 KB Output is correct
10 Correct 424 ms 229492 KB Output is correct
11 Correct 346 ms 230016 KB Output is correct
12 Correct 338 ms 228412 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 31 ms 30556 KB Output is correct
5 Correct 27 ms 31736 KB Output is correct
6 Correct 20 ms 18440 KB Output is correct
7 Correct 246 ms 228056 KB Output is correct
8 Correct 470 ms 229120 KB Output is correct
9 Correct 311 ms 230064 KB Output is correct
10 Correct 445 ms 229168 KB Output is correct
11 Correct 339 ms 229812 KB Output is correct
12 Correct 351 ms 228740 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 31 ms 30556 KB Output is correct
5 Correct 27 ms 31736 KB Output is correct
6 Correct 20 ms 18440 KB Output is correct
7 Correct 255 ms 227928 KB Output is correct
8 Correct 477 ms 228820 KB Output is correct
9 Correct 296 ms 231640 KB Output is correct
10 Correct 424 ms 229492 KB Output is correct
11 Correct 346 ms 230016 KB Output is correct
12 Correct 338 ms 228412 KB Output is correct
13 Correct 246 ms 228056 KB Output is correct
14 Correct 470 ms 229120 KB Output is correct
15 Correct 311 ms 230064 KB Output is correct
16 Correct 445 ms 229168 KB Output is correct
17 Correct 339 ms 229812 KB Output is correct
18 Correct 351 ms 228740 KB Output is correct
19 Correct 265 ms 228568 KB Output is correct
20 Correct 543 ms 232568 KB Output is correct
21 Correct 295 ms 232356 KB Output is correct
22 Correct 462 ms 231876 KB Output is correct
23 Correct 340 ms 229084 KB Output is correct
24 Correct 354 ms 229028 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 229828 KB Output is correct
2 Correct 480 ms 229508 KB Output is correct
3 Correct 303 ms 230496 KB Output is correct
4 Correct 427 ms 229472 KB Output is correct
5 Correct 348 ms 229080 KB Output is correct
6 Correct 345 ms 229404 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 229828 KB Output is correct
2 Correct 480 ms 229508 KB Output is correct
3 Correct 303 ms 230496 KB Output is correct
4 Correct 427 ms 229472 KB Output is correct
5 Correct 348 ms 229080 KB Output is correct
6 Correct 345 ms 229404 KB Output is correct
7 Incorrect 364 ms 229824 KB Output isn't correct
8 Halted 0 ms 0 KB -