#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
ll a[1<<20], b[1<<20], lazyA[1<<20], lazyB[1<<20];
void propagate(int i, int l, int r){
a[i] += lazyA[i] * (r-l+1), b[i] += lazyB[i] * (r-l+1);
if(l!=r) lazyA[i*2] += lazyA[i], lazyA[i*2+1] += lazyA[i], lazyB[i*2] += lazyB[i], lazyB[i*2+1] += lazyB[i];
lazyA[i] = lazyB[i] = 0;
}
void update(int i, int l, int r, int s, int e, ll av, ll bv){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazyA[i] = av, lazyB[i] = bv;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, av, bv);
update(i*2+1, m+1, r, s, e, av, bv);
a[i] = a[i*2] + a[i*2+1], b[i] = b[i*2] + b[i*2+1];
}
ll query(int i, int l, int r, int s, int e, ll t){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e) return a[i] * t + b[i];
int m = (l+r)>>1;
return query(i*2, l, m, s, e, t) + query(i*2+1, m+1, r, s, e, t);
}
} tree;
struct Event{
int type, y, l, r, a, b; /// type: 0 ���簢�� ����, 1 ���簢�� �߰�, 2 ����
Event(){}
Event(int type, int y, int l, int r, int a, int b): type(type), y(y), l(l), r(r), a(a), b(b){}
bool operator<(const Event &r)const{
if(y!=r.y) return y<r.y;
return type<r.type;
}
};
int n, q, MOD;
vector<Event> vec;
ll ans[50002];
int main(){
scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
for(int i=1; i<=n; i++){
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
if(x1>x2) swap(x1, x2);
if(y1>y2) swap(y1, y2);
x1++, y1++;
/// [x1, x2] [y1, y2] ������ ���ϴ� ������ �Է��� �ٲ�
vec.push_back(Event(1, y1, x1, x2, 1, -y1+1));
vec.push_back(Event(0, y2+1, x1, x2, -1, y2));
}
for(int i=1; i<=q; i++){
int x1, y1, x2, y2, v;
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
if(x1>x2) swap(x1, x2);
if(y1>y2) swap(y1, y2);
x1++, y1++;
vec.push_back(Event(2, y1-1, x1, x2, -1, i));
vec.push_back(Event(2, y2, x1, x2, 1, i));
}
sort(vec.begin(), vec.end());
const int MX = 300000;
for(Event &p: vec){
if(p.type <= 1) tree.update(1, 1, MX, p.l, p.r, p.a, p.b);
else ans[p.b] += tree.query(1, 1, MX, p.l, p.r, p.y) * p.a;
}
for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
15 ms |
1704 KB |
Output is correct |
5 |
Correct |
20 ms |
1740 KB |
Output is correct |
6 |
Correct |
15 ms |
1684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
15 ms |
1704 KB |
Output is correct |
5 |
Correct |
20 ms |
1740 KB |
Output is correct |
6 |
Correct |
15 ms |
1684 KB |
Output is correct |
7 |
Correct |
439 ms |
37380 KB |
Output is correct |
8 |
Correct |
234 ms |
38796 KB |
Output is correct |
9 |
Correct |
199 ms |
38592 KB |
Output is correct |
10 |
Correct |
230 ms |
38664 KB |
Output is correct |
11 |
Correct |
208 ms |
38704 KB |
Output is correct |
12 |
Correct |
208 ms |
38720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
15 ms |
1704 KB |
Output is correct |
5 |
Correct |
20 ms |
1740 KB |
Output is correct |
6 |
Correct |
15 ms |
1684 KB |
Output is correct |
7 |
Incorrect |
101 ms |
15704 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
15 ms |
1704 KB |
Output is correct |
5 |
Correct |
20 ms |
1740 KB |
Output is correct |
6 |
Correct |
15 ms |
1684 KB |
Output is correct |
7 |
Correct |
439 ms |
37380 KB |
Output is correct |
8 |
Correct |
234 ms |
38796 KB |
Output is correct |
9 |
Correct |
199 ms |
38592 KB |
Output is correct |
10 |
Correct |
230 ms |
38664 KB |
Output is correct |
11 |
Correct |
208 ms |
38704 KB |
Output is correct |
12 |
Correct |
208 ms |
38720 KB |
Output is correct |
13 |
Incorrect |
101 ms |
15704 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
166 ms |
16600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
166 ms |
16600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |