oj.uz

Submission #787497

# Submission time Handle Problem Language Result Execution time Memory
787497 2023-07-19T08:32:44 Z 8pete8 trapezoid (balkan11_trapezoid) C++14
14 / 100
 165 ms 20456 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 unsigned 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;
    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++;
            //for(int i=0;i<2*n;i++)cout<<seg[i].f<<" "<<seg[i].s<<'\n';
            //cout<<ans[i.s.s].f<<" "<<ans[i.s.s].s<<"A\n";
        }
        else {
            //cout<<"A\n";
            upd(getpos(i.f.s),ans[i.s.s]);
        }
    }
    pii ans=qry(0,n);
    cout<<ans.f<<" "<<ans.s<<'\n';
}

Subtask #1
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 232 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Expected int32, but "10313130667392" found
4 Incorrect 2 ms 456 KB Expected int64, but "9896467080883601408" found
5 Partially correct 3 ms 708 KB Partially correct
6 Incorrect 4 ms 884 KB Expected int64, but "9817663296286682560" found
7 Incorrect 5 ms 1104 KB Expected int64, but "15126877329018519552" found
8 Partially correct 7 ms 1228 KB Partially correct
9 Incorrect 14 ms 2288 KB Expected int32, but "2248786528710863832" found
10 Incorrect 27 ms 4420 KB Expected int64, but "13423941841486661120" found
11 Incorrect 35 ms 5388 KB Expected int64, but "17148325072771146318" found
12 Incorrect 75 ms 10444 KB Expected int32, but "9183932486774365824" found
13 Incorrect 89 ms 12196 KB Expected int64, but "14251591625020113344" found
14 Incorrect 107 ms 15260 KB Expected int64, but "15271637504803712768" found
15 Incorrect 119 ms 15984 KB Expected int64, but "10420374542398040064" found
16 Incorrect 124 ms 16820 KB Expected int32, but "6233362917342126368" found
17 Incorrect 132 ms 17880 KB Expected int64, but "10940917780872015856" found
18 Incorrect 124 ms 18604 KB Expected int64, but "12249444714630285294" found
19 Incorrect 157 ms 18776 KB Expected int32, but "5619696618904563712" found
20 Incorrect 165 ms 20456 KB Expected int64, but "18110925340075973263" found