#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a,b) for(i = a; i < b; i++)
#define ROF(i, b,a) for(i = b-1; i >= a; i--)
const int mxN = 4*1e5;
int n;
ll mod = 30013;
pii stree[4*mxN+1][2];
pii comp(pii a, pii b){
if (a.f == b.f){
return {a.f, (a.s+b.s)%mod};
} else {
if (a.f < b.f){
return b;
}
return a;
}
}
void upd(int t, pii v, bool w, int l = 0, int r = 4*n-1, int idx = 0){
if (l > t || r < t){
return;
}
if (l == r){
stree[idx][w] = v;
return;
}
int m = (l+r)/2;
upd(t,v,w,l,m,2*idx+1);
upd(t,v,w,m+1,r,2*idx+2);
stree[idx][w] = comp(stree[2*idx+1][w],stree[2*idx+2][w]);
return;
}
pii query(int tl, int tr, bool w, int l = 0, int r = 4*n-1, int idx = 0){
if (l > tr || r < tl){
return {0,0};
}
if (l >= tl && r <= tr){
/* if (tr == 18){
cout << l << "-" << r << " " << stree[idx][w].f << "," << stree[idx][w].s << '\n';
}*/
return stree[idx][w];
}
int m = (l+r)/2;
return comp(query(tl,tr,w,l,m,2*idx+1),query(tl,tr,w,m+1,r,2*idx+2));
}
bool c2(pii &a, pii &b){
return a.f < b.f;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i,j;
FOR (i,0,4*mxN+1){
stree[i][0] = {0,0};
stree[i][1] = {0,0};
}
cin >> n;
vector<pii> p(4*n);
int vals[n][4];
FOR(i,0,n){
cin >> p[4*i].f >> p[4*i+1].f >> p[4*i+2].f >> p[4*i+3].f;
}
FOR (i,0,4*n) p[i].s = i;
sort(p.begin(),p.end(),c2);
int nv = 0;
int last;
FOR(i,0,4*n){
last = p[i].f;
// cout << i << "," << last << " ";
FOR(j,i,4*n){
if (p[j].f == last){
vals[p[j].s/4][p[j].s%4] = nv;
p[j].f = nv;
} else {
break;
}
}
i = j-1;
nv++;
}
// cout << '\n';
pii res[n];
FOR (i,0,n) res[i] = {1,1};
int cnt[n][2];
memset(cnt,0,sizeof(cnt));
int idx;
pii temp;
FOR (i,0,4*n){
idx = p[i].s / 4;
//cout << idx << " " << p[i].f << ' ' << p[i].s << '\n';
if (cnt[idx][0] == 0 && cnt[idx][1] == 0){
if (p[i].s%4 < 2){
temp = query(0,vals[idx][2],1);
// cout << temp.f << "," << temp.s << '\n';
res[idx] = comp(res[idx],{temp.f+1,temp.s});
} else {
temp = query(0,vals[idx][0],0);
// cout << temp.f << "," << temp.s << '\n';
res[idx] = comp(res[idx],{temp.f+1,temp.s});
}
}
if (p[i].s%4 < 2){
cnt[idx][0]++;
if (cnt[idx][0] == 2){
// cout << res[idx].f << "\n";
upd(vals[idx][3],res[idx],1);
}
} else {
cnt[idx][1]++;
if (cnt[idx][1] == 2){
//cout << res[idx].f << '\n';
upd(vals[idx][1],res[idx],0);
}
}
}
// FOR (i,0,n) cout << vals[i][0] << "," << vals[i][1] << "," << vals[i][2] << "," << vals[i][3] << '\n';
pii tot = {0,0};
FOR (i,0,n){
// cout << res[i].f << ',' << res[i].s << '\n';
tot = comp(tot, res[i]);
}
cout << tot.f << " " << tot.s << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
50520 KB |
Output is correct |
| 2 |
Correct |
8 ms |
50520 KB |
Output is correct |
| 3 |
Correct |
8 ms |
50616 KB |
Output is correct |
| 4 |
Correct |
9 ms |
50612 KB |
Output is correct |
| 5 |
Correct |
10 ms |
50780 KB |
Output is correct |
| 6 |
Correct |
12 ms |
50780 KB |
Output is correct |
| 7 |
Correct |
12 ms |
51036 KB |
Output is correct |
| 8 |
Correct |
14 ms |
51036 KB |
Output is correct |
| 9 |
Correct |
24 ms |
51800 KB |
Output is correct |
| 10 |
Correct |
31 ms |
53084 KB |
Output is correct |
| 11 |
Correct |
43 ms |
53584 KB |
Output is correct |
| 12 |
Correct |
89 ms |
56892 KB |
Output is correct |
| 13 |
Correct |
102 ms |
58196 KB |
Output is correct |
| 14 |
Correct |
121 ms |
59468 KB |
Output is correct |
| 15 |
Correct |
134 ms |
59952 KB |
Output is correct |
| 16 |
Correct |
140 ms |
60756 KB |
Output is correct |
| 17 |
Correct |
164 ms |
61264 KB |
Output is correct |
| 18 |
Correct |
114 ms |
62036 KB |
Output is correct |
| 19 |
Correct |
157 ms |
62700 KB |
Output is correct |
| 20 |
Correct |
171 ms |
63384 KB |
Output is correct |
