oj.uz

Submission #787704

# Submission time Handle Problem Language Result Execution time Memory
787704 2023-07-19T11:19:27 Z 8pete8 trapezoid (balkan11_trapezoid) C++14
100 / 100
 162 ms 18800 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<pii,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=2*1e5+1,mx=1e6;
#define int long long
pii seg[3*mxn+10];
//mx size + way
int n;
pii comp(pii a,pii b){
    pii tmp=max(a,b);
    if(a.f==b.f)tmp.s=(a.s+b.s)%30013;
    if(tmp.f==0)tmp.s=1;
    return tmp;
}
void upd(int pos,pii val){
    pos+=n;
    seg[pos]=comp(seg[pos],val);
    for(;pos>1;pos>>=1)seg[pos>>1]=comp(seg[pos],seg[pos^1]);
}
pii qry(int l,int r){
    pii ans={0,0};
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
        if(l&1)ans=comp(ans,seg[l++]);
        if((r&1))ans=comp(ans,seg[--r]);
    }
    if(ans.f==0)ans.s=1;
    return ans;
}
vector<int>up;
int getpos(int val){return lb(all(up),val)-up.begin();}
pii ans[mxn+10];
int32_t main(){
    //bot start = qry the up start
    //bot end = update up end
    cin>>n;
    vector<ppii>v;
    for(int i=0;i<n;i++){
        pii a,b;cin>>a.s>>b.s>>a.f>>b.f;
        //up start, up end,bot start, bot end
        up.pb(a.s);
        up.pb(b.s);
        v.pb({a,{1,i}});
        v.pb({b,{-1,i}});
    }
    sort(all(up));
    sort(all(v));
    n*=2;
    for(auto i:v){
        if(i.s.f==1){
            int pos=getpos(i.f.s);
            ans[i.s.s]=qry(0,pos);
            ans[i.s.s].f++;
        }
        else upd(getpos(i.f.s),ans[i.s.s]);
    }
    pii ans=qry(0,n);
    cout<<ans.f<<" "<<ans.s<<'\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 832 KB Output is correct
7 Correct 5 ms 1088 KB Output is correct
8 Correct 7 ms 1228 KB Output is correct
9 Correct 15 ms 2248 KB Output is correct
10 Correct 28 ms 4412 KB Output is correct
11 Correct 37 ms 5300 KB Output is correct
12 Correct 77 ms 10088 KB Output is correct
13 Correct 97 ms 11664 KB Output is correct
14 Correct 116 ms 14244 KB Output is correct
15 Correct 145 ms 15104 KB Output is correct
16 Correct 143 ms 15764 KB Output is correct
17 Correct 149 ms 16684 KB Output is correct
18 Correct 133 ms 17232 KB Output is correct
19 Correct 148 ms 17292 KB Output is correct
20 Correct 162 ms 18800 KB Output is correct