#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MOD 30013
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define f first
#define s second
int n, stc[MAXN * 4], stn[MAXN * 4];
pair<int, int> sp[MAXN], ep[MAXN];
pair<int, short> dp[MAXN];
queue<pair<int, int>> lz[MAXN * 4];
void push_n(int i, int l, int r){
while(!lz[i].empty()){
auto lzi = lz[i].front(); lz[i].pop();
// if(lzi.f != 0) cout << " MGMGMG " << i << " => " << (stn[i] * (lzi.f != 0) + lzi.s) << endl;
stn[i] = (stn[i] * (lzi.f != 0) + lzi.s) % MOD;
if(l != r) lz[i * 2].push(lzi), lz[i * 2 + 1].push(lzi);
}
}
int query_n(int i, int l, int r, int qry){
push_n(i, l, r);
if(qry < l || r < qry) return 0;
if(l == r) return stn[i];
return (query_n(i * 2, l, (l + r) / 2, qry) + query_n(i * 2 + 1, (l + r) / 2 + 1, r, qry)) % MOD;
}
void update_n(int i, int l, int r, pair<int, int> rng, pair<int, int> upd){
// if(rng.f == 5 && rng.s == 14) cout << "HERE -> " << i << " of rng " << l << " " << r << endl;
push_n(i, l, r);
if(rng.s < l || r < rng.f) return;
if(rng.f <= l && r <= rng.s) {
// cout << " \--> HERERO " << endl;
lz[i].push(upd);
push_n(i, l, r);
return;
}
update_n(i * 2, l, (l + r) / 2, rng, upd);
update_n(i * 2 + 1, (l + r) / 2 + 1, r, rng, upd);
}
int query_c(int i, int l, int r, pair<int, int> rng){
if(rng.second < l || r < rng.first) return 0;
if(rng.first <= l && r <= rng.second) return stc[i];
return max(query_c(i * 2, l, (l + r) / 2, rng), query_c(i * 2 + 1, (l + r) / 2 + 1, r, rng));
}
void update_c(int i, int l, int r, pair<int, int> upd){
if(upd.f < l || r < upd.f) return;
if(l == r) {
stc[i] = upd.s;
return;
}
update_c(i * 2, l, (l + r) / 2, upd);
update_c(i * 2 + 1, (l + r) / 2 + 1, r, upd);
stc[i] = max(stc[i * 2], stc[i * 2 + 1]);
}
int main(){
cin >> n;
vector<pair<int, pair<int, int>>> ple;
FOR(i, 1, n){
cin >> sp[i].f >> ep[i].f;
cin >> sp[i].s >> ep[i].s;
ple.push_back({sp[i].s, {0, i}});
ple.push_back({ep[i].s, {1, i}});
}
// coordinate compression
vector<pair<int, pair<int, int>>> pls;
sort(begin(ple), end(ple));
FOR(i, 1, 2 * n){
if(ple[i - 1].s.f == 0){
sp[ple[i - 1].s.s].s = i;
pls.push_back({sp[ple[i - 1].s.s].f, {0, ple[i - 1].s.s}});
}else{
ep[ple[i - 1].s.s].s = i;
pls.push_back({ep[ple[i - 1].s.s].f, {1, ple[i - 1].s.s}});
}
}
sort(begin(pls), end(pls));
FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
update_n(1, 0, 2 * n, {0, 2 * n}, {0, 1});
/* FOR(i, 0, 2*n){
cout << " " << query_n(1, 0, 2*n, i);
}
cout << endl;
FOR(i, 0, 2*n){
cout << " " << query_c(1, 0, 2*n, {i, i});
}
cout << endl; */
for(auto pi : pls){
int i = pi.s.s;
if(pi.s.f == 0){ // start point
dp[i].f = query_c(1, 0, 2 * n, {0, sp[i].s - 1}) + 1;
dp[i].s = query_n(1, 0, 2 * n, sp[i].s - 1) % MOD;
// cout << "DP " << i << " EQUALS " << dp[i].f << " of ct " << dp[i].s << endl;
}else{
int qi = query_c(1, 0, 2 * n, {0, ep[i].s - 1});
if(qi > dp[i].f) goto update;
int lo = ep[i].s, hi = 2 * n;
if(qi < dp[i].f){
while(lo < hi){
int mid = (lo + hi + 1) / 2;
// cout << " FINDING NEMOi FOR THE BELOW " << 0 << " to " << mid << " GIVES " << query_c(1, 0, 2 * n, {0, mid}) << endl;
if(query_c(1, 0, 2 * n, {0, mid}) < dp[i].f){
lo = mid;
}else{
hi = mid - 1;
}
}
// replace num valid ways with dp[i].s for range (ep[i].s)...lo
update_n(1, 0, 2 * n, {ep[i].s, lo}, {0, dp[i].s});
// cout << " ALERT 1: we update " << ep[i].s << " TO " << lo << " with complete refurbish to " << dp[i].s << endl;
/* FOR(i, 0, 2*n){
cout << " " << query_n(1, 0, 2*n, i);
}
cout << endl;
FOR(i, 0, 2*n){
cout << " " << query_c(1, 0, 2*n, {i, i});
}
cout << endl; */
if(lo == 2 * n) goto update;
lo ++;
}
int si = lo;
if(query_c(1, 0, 2 * n, {0, lo}) != dp[i].f) goto update;
hi = 2 * n;
while(lo < hi){
// cout << ((lo + hi) / 2) << " => " << query_c(i, 0, 2 * n, {0, (lo + hi) / 2}) << endl;
int mid = (lo + hi + 1) / 2;
if(query_c(1, 0, 2 * n, {0, mid}) == dp[i].f){
lo = mid;
}else{
hi = mid - 1;
}
}
// add num valid ways with dp[i].s for range si...lo
update_n(1, 0, 2 * n, {si, lo}, {1, dp[i].s});
/*cout << " ALERT 2: we update " << si << " TO " << lo << " with add to " << dp[i].s << endl;
FOR(j, 0, 2*n){
cout << " " << query_n(1, 0, 2*n, j);
}
cout << endl;
FOR(j, 0, 2*n){
cout << " " << query_c(1, 0, 2*n, {j, j});
}
cout << endl;*/
}
update:;
if(pi.s.f == 1) {
// cout << " => " << dp[i].f << endl;
update_c(1, 0, 2 * n, {ep[i].s, dp[i].f});
/* cout << " ALERT 3" << endl;
FOR(i, 0, 2*n){
cout << " " << query_c(1, 0, 2*n, {i, i});
}
cout << endl; */
}
}
int cr = query_c(1, 0, 2 * n, {0, 2 * n});
cout << cr;
int nr = 0;
FOR(i, 1, n) if(dp[i].f == cr) nr = (nr + dp[i].s) % MOD;
cout << " " << nr << endl;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:90:49: warning: iteration 400020 invokes undefined behavior [-Waggressive-loop-optimizations]
90 | FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
| ~~~~~~~^~~
trapezoid.cpp:5:39: note: within this loop
5 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
90 | FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
| ~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:90:5: note: in expansion of macro 'FOR'
90 | FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
| ^~~
trapezoid.cpp:90:49: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [1600080, 3200159] is out of the bounds [0, 1600080] of object 'stn' with type 'int [400020]' [-Warray-bounds]
90 | FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
| ~~~~~~~^~~
trapezoid.cpp:9:23: note: 'stn' declared here
9 | int n, stc[MAXN * 4], stn[MAXN * 4];
| ^~~
trapezoid.cpp:90:40: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [1600080, 3200159] is out of the bounds [0, 1600080] of object 'stc' with type 'int [400020]' [-Warray-bounds]
90 | FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
| ~~~~~~~^~~~~~~~~~~~
trapezoid.cpp:9:8: note: 'stc' declared here
9 | int n, stc[MAXN * 4], stn[MAXN * 4];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
43 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
33 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
36 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
43 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
40 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
42 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
35 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
38 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
38 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
37 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
37 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
39 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
38 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
47 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
