#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;
}
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
- |