/*
希望能進全國賽
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct node{
int a,b,c,d;
};
const int mxn=2e5+5;
node num[mxn];
vector<pair<int,ll>> as[mxn],bs[mxn];
pair<int,ll> ans[mxn];
pair<int,ll> segtree[mxn*4];
map<int,int> idup,iddown;
int cntup=0;
int cntdown=0;
pair<int,ll> comb(pair<int,ll> a,pair<int,ll> b){
if(a.f==b.f){
return {a.f,a.s+b.s};
}
return max(a,b);
}
void update(int pos,pair<int,ll> val,int l=1,int r=cntdown,int v=1){
if(l==r){
segtree[v]=comb(segtree[v],val);
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(pos,val,l,mid,v*2);
else update(pos,val,mid+1,r,v*2+1);
segtree[v]=comb(segtree[v*2],segtree[v*2+1]);
}
pair<int,ll> query(int tl,int tr,int l=1,int r=cntdown,int v=1){
if(tl>tr){
return {0,0};
}
if(tl<=l and r<=tr){
return segtree[v];
}
int mid=(l+r)/2;
return comb(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
int main() {_
//setIO("wayne");
int n;
cin>>n;
for(int i=1;i<=n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
num[i]={a,b,c,d};
idup[a]++;
idup[b]++;
iddown[c]++;
iddown[d]++;
}
for(auto &v:idup){
cntup++;
v.s=cntup;
}
for(auto &v:iddown){
cntdown++;
v.s=cntdown;
}
for(int i=1;i<=n;i++){
as[idup[num[i].a]].push_back({iddown[num[i].c],i});
bs[idup[num[i].b]].push_back({iddown[num[i].d],i});
}
for(int i=1;i<=cntup;i++){
for(auto v:as[i]){
//cout<<"a "<<v.s<<'\n';
pair<int,ll> tmp=query(1,v.f-1);
ans[v.s]={tmp.f+1,tmp.s+(tmp.f==0)};
}
for(auto v:bs[i]){
//cout<<"b "<<v.s<<'\n';
update(v.f,ans[v.s]);
}
//cout<<'\n';
}
cout<<segtree[1].f<<' '<<segtree[1].s<<'\n';
return 0;
}
//maybe its multiset not set
Compilation message
trapezoid.cpp: In function 'void setIO(std::string)':
trapezoid.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
9812 KB |
Expected int32, but "10313130667392" found |
| 4 |
Incorrect |
7 ms |
10032 KB |
Expected int32, but "-8550276992825950208" found |
| 5 |
Partially correct |
9 ms |
10324 KB |
Partially correct |
| 6 |
Incorrect |
11 ms |
10836 KB |
Expected int32, but "-8629080777422869056" found |
| 7 |
Incorrect |
13 ms |
11108 KB |
Expected int32, but "-3319866744691032064" found |
| 8 |
Partially correct |
17 ms |
11604 KB |
Partially correct |
| 9 |
Incorrect |
37 ms |
13524 KB |
Expected int32, but "2248786528710863832" found |
| 10 |
Incorrect |
57 ms |
17412 KB |
Expected int32, but "-5022802232222890496" found |
| 11 |
Incorrect |
66 ms |
18492 KB |
Expected int32, but "-1298419000938405298" found |
| 12 |
Incorrect |
157 ms |
27908 KB |
Expected int32, but "9183932486774365824" found |
| 13 |
Incorrect |
204 ms |
30652 KB |
Expected int32, but "-4195152448689438272" found |
| 14 |
Incorrect |
226 ms |
37272 KB |
Expected int32, but "-3175106568905838848" found |
| 15 |
Incorrect |
297 ms |
39104 KB |
Expected int32, but "-8026369531311511552" found |
| 16 |
Incorrect |
300 ms |
40456 KB |
Expected int32, but "6233362917342126368" found |
| 17 |
Incorrect |
314 ms |
41836 KB |
Expected int32, but "-7505826292837535760" found |
| 18 |
Incorrect |
264 ms |
42992 KB |
Expected int32, but "-6197299359079266322" found |
| 19 |
Incorrect |
280 ms |
42932 KB |
Expected int32, but "5619696618904563712" found |
| 20 |
Incorrect |
368 ms |
45532 KB |
Expected int32, but "-335818733633578353" found |
