#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> vx;
struct segTree{
ll a[1<<20], b[1<<20], aSum[1<<20], bSum[1<<20];
void update(int i, int l, int r, int s, int e, ll av, ll bv){
if(r<s || e<l) return;
if(s<=l && r<=e){
a[i] += av, b[i] += bv;
aSum[i] += av * (vx[r+1] - vx[l]), bSum[i] += bv * (vx[r+1] - vx[l]);
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);
aSum[i] = aSum[i*2] + aSum[i*2+1] + a[i] * (vx[r+1] - vx[l]);
bSum[i] = bSum[i*2] + bSum[i*2+1] + b[i] * (vx[r+1] - vx[l]);
}
ll query(int i, int l, int r, int s, int e, ll t, ll aup=0, ll bup=0){
if(r<s || e<l) return 0;
if(s<=l && r<=e) return (aSum[i] + aup * (vx[r+1] - vx[l])) * t + (bSum[i] + bup * (vx[r+1] - vx[l]));
int m = (l+r)>>1;
return query(i*2, l, m, s, e, t, aup + a[i], bup + b[i]) + query(i*2+1, m+1, r, s, e, t, aup + a[i], bup + b[i]);
}
} 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:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | 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 |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
15 ms |
2752 KB |
Output is correct |
5 |
Correct |
15 ms |
2852 KB |
Output is correct |
6 |
Correct |
14 ms |
2728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
15 ms |
2752 KB |
Output is correct |
5 |
Correct |
15 ms |
2852 KB |
Output is correct |
6 |
Correct |
14 ms |
2728 KB |
Output is correct |
7 |
Correct |
144 ms |
22792 KB |
Output is correct |
8 |
Correct |
225 ms |
34716 KB |
Output is correct |
9 |
Correct |
203 ms |
27132 KB |
Output is correct |
10 |
Correct |
237 ms |
35384 KB |
Output is correct |
11 |
Correct |
211 ms |
35484 KB |
Output is correct |
12 |
Correct |
193 ms |
27188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
15 ms |
2752 KB |
Output is correct |
5 |
Correct |
15 ms |
2852 KB |
Output is correct |
6 |
Correct |
14 ms |
2728 KB |
Output is correct |
7 |
Correct |
192 ms |
28524 KB |
Output is correct |
8 |
Correct |
244 ms |
34932 KB |
Output is correct |
9 |
Correct |
200 ms |
35448 KB |
Output is correct |
10 |
Correct |
257 ms |
35548 KB |
Output is correct |
11 |
Correct |
238 ms |
35552 KB |
Output is correct |
12 |
Correct |
213 ms |
35488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
15 ms |
2752 KB |
Output is correct |
5 |
Correct |
15 ms |
2852 KB |
Output is correct |
6 |
Correct |
14 ms |
2728 KB |
Output is correct |
7 |
Correct |
144 ms |
22792 KB |
Output is correct |
8 |
Correct |
225 ms |
34716 KB |
Output is correct |
9 |
Correct |
203 ms |
27132 KB |
Output is correct |
10 |
Correct |
237 ms |
35384 KB |
Output is correct |
11 |
Correct |
211 ms |
35484 KB |
Output is correct |
12 |
Correct |
193 ms |
27188 KB |
Output is correct |
13 |
Correct |
192 ms |
28524 KB |
Output is correct |
14 |
Correct |
244 ms |
34932 KB |
Output is correct |
15 |
Correct |
200 ms |
35448 KB |
Output is correct |
16 |
Correct |
257 ms |
35548 KB |
Output is correct |
17 |
Correct |
238 ms |
35552 KB |
Output is correct |
18 |
Correct |
213 ms |
35488 KB |
Output is correct |
19 |
Correct |
215 ms |
28836 KB |
Output is correct |
20 |
Correct |
250 ms |
35140 KB |
Output is correct |
21 |
Correct |
260 ms |
35548 KB |
Output is correct |
22 |
Correct |
266 ms |
35872 KB |
Output is correct |
23 |
Correct |
276 ms |
35736 KB |
Output is correct |
24 |
Correct |
207 ms |
35756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
164 ms |
25760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
164 ms |
25760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |