#include <bits/stdc++.h>
using namespace std;
#define inf 1023456789
#define linf 1023456789123456789ll
#define pii pair<int,int>
#define pipii pair<int, pii >
#define pll pair<long long,long long>
#define vint vector<int>
#define vvint vector<vint >
#define ll long long
#define pdd pair<double, double>
#define DEBUG
#ifdef DEBUG
#define db(x) cerr << #x << " = " << x << endl
#else
#define db(x)
#endif
struct node
{
int from, to;
ll value;
ll lazy;
node *left, *right;
bool am_leaf;
node(int f, int t, ll v, node *l = NULL, node *r = NULL, ll laz = 0) : from(f), to(t), value(v), left(l), right(r), lazy(laz)
{
am_leaf = left == NULL;
}
ll get(int a, int b)
{
if(b <= from || a >= to) return 0;
if(a <= from && b >= to) return value;
ll length = min(b, to) - max(a, from);
if(am_leaf) return value/(to-from) * length;
return left->get(a, b) + right->get(a,b) + lazy * length;
}
node *add(int a, int b, ll val)
{
if(b <= from || a >= to) return this;
if(a <= from && b >= to)
{
return new node(from, to, value+val*(to-from), left, right, lazy+val);
}
node *l = left->add(a, b, val);
node *r = right->add(a, b, val);
return new node(from, to, l->value+r->value+lazy*(to-from) , l, r, lazy);
}
};
node *segtree(vector<int>& coors, int a, int b) //[]
{
if(b - a == 1)
{
return new node(coors[a], coors[b], 0);
}
int mid = (a+b)/2;
node *left = segtree(coors, a, mid);
node *right = segtree(coors, mid, b);
return new node(coors[a], coors[b], 0, left, right);
}
map<int, node*> current, cumulative;
ll sum_before(int x, int y1, int y2)
{
node *cur_seg = current.lower_bound(x)->second;
node *cum_seg = cumulative.lower_bound(x)->second;
return cum_seg->get(y1, y2) + cur_seg->get(y1, y2)*x;
}
int main()
{
int r, c, n, q;
ll mod;
scanf("%d %d %d %d %lld", &r, &c, &n, &q, &mod);
vector<int> x1(n), y1(n), x2(n), y2(n);
vector<pair<int, pii > > event;
set<int> ys;
int maxx = 0;
for(int i=0; i<n; i++)
{
scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
if(x1[i] > x2[i])swap(x1[i], x2[i]);
if(y1[i] > y2[i])swap(y1[i], y2[i]);
ys.insert(y1[i]);
ys.insert(y2[i]);
current[x1[i]] = NULL;
current[x2[i]] = NULL;
cumulative[x1[i]] = NULL;
cumulative[x2[i]] = NULL;
maxx = max(maxx, x2[i]);
event.push_back(pipii(x1[i], pii(i, 1)));
event.push_back(pipii(x2[i], pii(i, -1)));
}
vector<int> ysvec;
for(set<int>::iterator it = ys.begin(); it != ys.end(); it++)
{
ysvec.push_back(*it);
}
node *ccur = segtree(ysvec, 0, ysvec.size()-1), *ccum = segtree(ysvec, 0, ysvec.size()-1);
sort(event.begin(), event.end());
for(int i=0; i<event.size(); i++)
{
int x = event[i].first, id = event[i].second.first, type = event[i].second.second;
if(current[x] == NULL)
{
current[x] = ccur;
cumulative[x] = ccum;
}
ccur = ccur->add(y1[id], y2[id], type);
if(type == 1)
{
ccum = ccum->add(y1[id], y2[id], -x);
}
else
{
ccum = ccum->add(y1[id], y2[id], x);
}
}
//queries incoming, brace yourselves
ll l = 0;
for(int i=0; i<q; i++)
{
int x1, y1, x2, y2;
ll v;
scanf("%d %d %d %d %lld", &x1, &y1, &x2, &y2, &v);
x1 = (x1+(l%mod)*v)%mod;
x2 = (x2+(l%mod)*v)%mod;
y1 = (y1+(l%mod)*v)%mod;
y2 = (y2+(l%mod)*v)%mod;
if(x1 > x2)swap(x1, x2);
if(y1 > y2)swap(y1, y2);
x2 = min(x2, maxx);
x1 = min(x1, maxx);
l = sum_before(x2, y1, y2) - sum_before(x1, y1, y2);
printf("%lld\n", l);
}
return 0;
}
Compilation message
Main.cpp: In constructor 'node::node(int, int, long long int, node*, node*, long long int)':
Main.cpp:26:15: warning: 'node::right' will be initialized after [-Wreorder]
26 | node *left, *right;
| ^~~~~
Main.cpp:25:5: warning: 'long long int node::lazy' [-Wreorder]
25 | ll lazy;
| ^~~~
Main.cpp:29:2: warning: when initialized here [-Wreorder]
29 | node(int f, int t, ll v, node *l = NULL, node *r = NULL, ll laz = 0) : from(f), to(t), value(v), left(l), right(r), lazy(laz)
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0; i<event.size(); i++)
| ~^~~~~~~~~~~~~
Main.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d %d %d %d %lld", &r, &c, &n, &q, &mod);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d %d %d %d %lld", &x1, &y1, &x2, &y2, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1612 KB |
Output is correct |
2 |
Correct |
4 ms |
1864 KB |
Output is correct |
3 |
Correct |
4 ms |
1868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1612 KB |
Output is correct |
2 |
Correct |
4 ms |
1864 KB |
Output is correct |
3 |
Correct |
4 ms |
1868 KB |
Output is correct |
4 |
Correct |
70 ms |
23252 KB |
Output is correct |
5 |
Correct |
64 ms |
19648 KB |
Output is correct |
6 |
Correct |
87 ms |
23548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1612 KB |
Output is correct |
2 |
Correct |
4 ms |
1864 KB |
Output is correct |
3 |
Correct |
4 ms |
1868 KB |
Output is correct |
4 |
Correct |
70 ms |
23252 KB |
Output is correct |
5 |
Correct |
64 ms |
19648 KB |
Output is correct |
6 |
Correct |
87 ms |
23548 KB |
Output is correct |
7 |
Correct |
592 ms |
242852 KB |
Output is correct |
8 |
Correct |
2037 ms |
380652 KB |
Output is correct |
9 |
Correct |
1131 ms |
398020 KB |
Output is correct |
10 |
Correct |
2029 ms |
357460 KB |
Output is correct |
11 |
Correct |
1577 ms |
243104 KB |
Output is correct |
12 |
Correct |
1800 ms |
389500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1612 KB |
Output is correct |
2 |
Correct |
4 ms |
1864 KB |
Output is correct |
3 |
Correct |
4 ms |
1868 KB |
Output is correct |
4 |
Correct |
70 ms |
23252 KB |
Output is correct |
5 |
Correct |
64 ms |
19648 KB |
Output is correct |
6 |
Correct |
87 ms |
23548 KB |
Output is correct |
7 |
Correct |
738 ms |
233200 KB |
Output is correct |
8 |
Correct |
2211 ms |
376392 KB |
Output is correct |
9 |
Correct |
1291 ms |
398360 KB |
Output is correct |
10 |
Correct |
2013 ms |
354256 KB |
Output is correct |
11 |
Correct |
1458 ms |
243564 KB |
Output is correct |
12 |
Correct |
1457 ms |
384528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1612 KB |
Output is correct |
2 |
Correct |
4 ms |
1864 KB |
Output is correct |
3 |
Correct |
4 ms |
1868 KB |
Output is correct |
4 |
Correct |
70 ms |
23252 KB |
Output is correct |
5 |
Correct |
64 ms |
19648 KB |
Output is correct |
6 |
Correct |
87 ms |
23548 KB |
Output is correct |
7 |
Correct |
592 ms |
242852 KB |
Output is correct |
8 |
Correct |
2037 ms |
380652 KB |
Output is correct |
9 |
Correct |
1131 ms |
398020 KB |
Output is correct |
10 |
Correct |
2029 ms |
357460 KB |
Output is correct |
11 |
Correct |
1577 ms |
243104 KB |
Output is correct |
12 |
Correct |
1800 ms |
389500 KB |
Output is correct |
13 |
Correct |
738 ms |
233200 KB |
Output is correct |
14 |
Correct |
2211 ms |
376392 KB |
Output is correct |
15 |
Correct |
1291 ms |
398360 KB |
Output is correct |
16 |
Correct |
2013 ms |
354256 KB |
Output is correct |
17 |
Correct |
1458 ms |
243564 KB |
Output is correct |
18 |
Correct |
1457 ms |
384528 KB |
Output is correct |
19 |
Correct |
970 ms |
410388 KB |
Output is correct |
20 |
Correct |
2024 ms |
396336 KB |
Output is correct |
21 |
Correct |
1211 ms |
398404 KB |
Output is correct |
22 |
Correct |
1967 ms |
371564 KB |
Output is correct |
23 |
Correct |
1390 ms |
249584 KB |
Output is correct |
24 |
Correct |
1653 ms |
404380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
477 ms |
214892 KB |
Output is correct |
2 |
Correct |
2008 ms |
353432 KB |
Output is correct |
3 |
Correct |
1028 ms |
398224 KB |
Output is correct |
4 |
Correct |
1801 ms |
336008 KB |
Output is correct |
5 |
Correct |
1146 ms |
236152 KB |
Output is correct |
6 |
Correct |
1446 ms |
363768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
477 ms |
214892 KB |
Output is correct |
2 |
Correct |
2008 ms |
353432 KB |
Output is correct |
3 |
Correct |
1028 ms |
398224 KB |
Output is correct |
4 |
Correct |
1801 ms |
336008 KB |
Output is correct |
5 |
Correct |
1146 ms |
236152 KB |
Output is correct |
6 |
Correct |
1446 ms |
363768 KB |
Output is correct |
7 |
Correct |
1006 ms |
410020 KB |
Output is correct |
8 |
Correct |
2230 ms |
396404 KB |
Output is correct |
9 |
Correct |
1321 ms |
398388 KB |
Output is correct |
10 |
Correct |
2009 ms |
371680 KB |
Output is correct |
11 |
Correct |
1320 ms |
249292 KB |
Output is correct |
12 |
Correct |
1524 ms |
404004 KB |
Output is correct |