#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> vx;
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] * (vx[r+1] - vx[l]), b[i] += lazyB[i] * (vx[r+1] - vx[l]);
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; ll y, l, r, a, b; /// type: 0 ���簢�� ����, 1 ���簢�� �߰�, 2 ����
Event(){}
Event(int type, ll y, ll l, ll r, ll a, ll 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++){
ll x1, y1, x2, y2;
scanf("%lld %lld %lld %lld", &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++){
ll x1, y1, x2, y2, v;
scanf("%lld %lld %lld %lld %lld", &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));
}
for(Event &p: vec){
vx.push_back(p.l);
vx.push_back(p.r+1);
}
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
for(Event &p: vec){
p.l = lower_bound(vx.begin(), vx.end(), p.l) - vx.begin();
p.r = lower_bound(vx.begin(), vx.end(), p.r+1) - vx.begin() - 1;
}
sort(vec.begin(), vec.end());
const int MX = (int)vx.size() - 2;
for(Event &p: vec){
if(p.type <= 1) tree.update(1, 0, MX, p.l, p.r, p.a, p.b);
else ans[p.b] += tree.query(1, 0, 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:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
18 ms |
2644 KB |
Output is correct |
5 |
Correct |
22 ms |
2644 KB |
Output is correct |
6 |
Correct |
18 ms |
2616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
18 ms |
2644 KB |
Output is correct |
5 |
Correct |
22 ms |
2644 KB |
Output is correct |
6 |
Correct |
18 ms |
2616 KB |
Output is correct |
7 |
Correct |
285 ms |
21836 KB |
Output is correct |
8 |
Correct |
278 ms |
34260 KB |
Output is correct |
9 |
Correct |
260 ms |
25828 KB |
Output is correct |
10 |
Correct |
309 ms |
34140 KB |
Output is correct |
11 |
Correct |
297 ms |
34116 KB |
Output is correct |
12 |
Correct |
238 ms |
25948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
18 ms |
2644 KB |
Output is correct |
5 |
Correct |
22 ms |
2644 KB |
Output is correct |
6 |
Correct |
18 ms |
2616 KB |
Output is correct |
7 |
Correct |
262 ms |
34272 KB |
Output is correct |
8 |
Correct |
323 ms |
34348 KB |
Output is correct |
9 |
Correct |
243 ms |
34124 KB |
Output is correct |
10 |
Correct |
309 ms |
34352 KB |
Output is correct |
11 |
Correct |
293 ms |
34292 KB |
Output is correct |
12 |
Correct |
250 ms |
34268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
18 ms |
2644 KB |
Output is correct |
5 |
Correct |
22 ms |
2644 KB |
Output is correct |
6 |
Correct |
18 ms |
2616 KB |
Output is correct |
7 |
Correct |
285 ms |
21836 KB |
Output is correct |
8 |
Correct |
278 ms |
34260 KB |
Output is correct |
9 |
Correct |
260 ms |
25828 KB |
Output is correct |
10 |
Correct |
309 ms |
34140 KB |
Output is correct |
11 |
Correct |
297 ms |
34116 KB |
Output is correct |
12 |
Correct |
238 ms |
25948 KB |
Output is correct |
13 |
Correct |
262 ms |
34272 KB |
Output is correct |
14 |
Correct |
323 ms |
34348 KB |
Output is correct |
15 |
Correct |
243 ms |
34124 KB |
Output is correct |
16 |
Correct |
309 ms |
34352 KB |
Output is correct |
17 |
Correct |
293 ms |
34292 KB |
Output is correct |
18 |
Correct |
250 ms |
34268 KB |
Output is correct |
19 |
Correct |
288 ms |
34524 KB |
Output is correct |
20 |
Correct |
330 ms |
34540 KB |
Output is correct |
21 |
Correct |
249 ms |
34264 KB |
Output is correct |
22 |
Correct |
305 ms |
34448 KB |
Output is correct |
23 |
Correct |
310 ms |
34420 KB |
Output is correct |
24 |
Correct |
300 ms |
34544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
230 ms |
25548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
230 ms |
25548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |