oj.uz

답안 #787499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787499 2023-07-19T08:34:42 Z 8pete8 사다리꼴 (balkan11_trapezoid) C++14
14 / 100
 163 ms 17844 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;
    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++;
            //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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Expected int32, but "10313130667392" found
4 Incorrect 1 ms 468 KB Expected int64, but "9896467080883601408" found
5 Partially correct 3 ms 724 KB Partially correct
6 Incorrect 4 ms 848 KB Expected int64, but "9817663296286682560" found
7 Incorrect 5 ms 976 KB Expected int64, but "15126877329018519552" found
8 Partially correct 7 ms 1228 KB Partially correct
9 Incorrect 14 ms 2092 KB Expected int32, but "2248786528710863832" found
10 Incorrect 28 ms 3900 KB Expected int64, but "13423941841486661120" found
11 Incorrect 34 ms 4720 KB Expected int64, but "17148325072771146318" found
12 Incorrect 75 ms 9128 KB Expected int32, but "9183932486774365824" found
13 Incorrect 97 ms 10672 KB Expected int64, but "14251591625020113344" found
14 Incorrect 107 ms 13356 KB Expected int64, but "15271637504803712768" found
15 Incorrect 122 ms 14136 KB Expected int64, but "10420374542398040064" found
16 Incorrect 129 ms 14660 KB Expected int32, but "6233362917342126368" found
17 Incorrect 130 ms 15672 KB Expected int64, but "10940917780872015856" found
18 Incorrect 123 ms 16204 KB Expected int64, but "12249444714630285294" found
19 Incorrect 135 ms 16212 KB Expected int32, but "5619696618904563712" found
20 Incorrect 163 ms 17844 KB Expected int64, but "18110925340075973263" found