답안 #707785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707785 2023-03-10T06:38:40 Z LittleOrange 사다리꼴 (balkan11_trapezoid) C++17
8 / 100
209 ms 51420 KB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll v,c;
    obj(): v(0),c(1){}
    obj(ll a, ll b): v(a), c(b){}
    obj operator+(const obj &o) const{
        return v==o.v?obj(v,c+o.c):v<o.v?o:*this;
    }
    obj operator|(const obj &o) const{
        return v==o.v?obj(v,max(c,o.c)):v<o.v?o:*this;
    }
};
struct segtree{
    ll n;
    vector<obj> dat;
    vector<obj> tag;
    segtree(ll N): n(N){
        dat.resize(n<<2);
        tag.resize(n<<2,obj(0,0));
    }
    void add(ll i, obj v){
        dat[i] = dat[i]+v;
        tag[i] = tag[i]+v;
    }
    void push(ll i){
        add(i<<1,tag[i]);
        add(i<<1|1,tag[i]);
        tag[i] = obj(0,0);
    }
    void add(ll i, ll l, ll r, ll ql, ll qr, obj v){
        if (ql<=l&&r<=qr){
            add(i,v);
        }else{
            ll m = l+r>>1;
            push(i);
            if (ql<=m) add(i<<1,l,m,ql,qr,v);
            if (qr>m) add(i<<1|1,m+1,r,ql,qr,v);
        }
    }
    void add(ll ql, ll qr, obj v){
        add(1,0,n-1,ql,qr,v);
    }
    obj query(ll i, ll l, ll r, ll x){
        if (l == r){
            return dat[i];
        }else{
            ll m = l+r>>1;
            push(i);
            if (x<=m) return query(i<<1,l,m,x);
            else return query(i<<1|1,m+1,r,x);
        }
    }
    obj query(ll x){
        if (x<0) return obj(0,1);
        return query(1,0,n-1,x);
    }
};
struct evt{
    ll a,b,c,d;
    bool operator<(const evt &o) const{
        return b>o.b;
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<evt> a(n);
    for(auto &o : a) cin >> o.a >> o.b >> o.c >> o.d;
    sort(a.begin(),a.end(),[&](const evt &a, const evt &b){return a.a<b.a;});
    vector<ll> x;
    for(auto &o : a) x.push_back(o.a),x.push_back(o.b),x.push_back(o.c),x.push_back(o.d);
    sort(x.begin(),x.end());
    x.resize(unique(x.begin(),x.end())-x.begin());
    auto gx = [&](ll i){return lower_bound(x.begin(),x.end(),i)-x.begin();};
    segtree t(x.size());
    obj ans = obj(0,1);
    priority_queue<evt> q;
    for(evt o : a){
        while (!q.empty()&&q.top().b<o.a){
            evt z = q.top();
            q.pop();
            t.add(gx(z.d),x.size()-1,obj(z.a,z.c));
        }
        obj g = t.query(gx(o.c)-1);
        g = obj(g.v+1,g.c);
        ans = ans | g;
        q.push({g.v,o.b,g.c,o.d});
    }
    cout << ans.v << " " << ans.c << '\n';
}

Compilation message

trapezoid.cpp: In member function 'void segtree::add(ll, ll, ll, ll, ll, obj)':
trapezoid.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |             ll m = l+r>>1;
      |                    ~^~
trapezoid.cpp: In member function 'obj segtree::query(ll, ll, ll, ll)':
trapezoid.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             ll m = l+r>>1;
      |                    ~^~
# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 212 KB Partially correct
2 Partially correct 1 ms 316 KB Partially correct
3 Incorrect 1 ms 468 KB Expected int32, but "3389517342720" found
4 Incorrect 1 ms 596 KB Expected int32, but "7117945929880436736" found
5 Partially correct 3 ms 1492 KB Partially correct
6 Incorrect 5 ms 2132 KB Expected int32, but "3505721401087858624" found
7 Incorrect 6 ms 1744 KB Expected int32, but "7714248878884782080" found
8 Partially correct 8 ms 2732 KB Partially correct
9 Incorrect 17 ms 5844 KB Expected int32, but "522405817371529289" found
10 Incorrect 29 ms 7268 KB Expected int32, but "7012317025184523008" found
11 Incorrect 48 ms 13972 KB Expected int32, but "8326539073436363494" found
12 Incorrect 94 ms 28608 KB Expected int32, but "8737773565241323904" found
13 Incorrect 114 ms 32980 KB Expected int32, but "-4195152448689438272" found
14 Incorrect 151 ms 40360 KB Expected int32, but "7908491273097169920" found
15 Incorrect 154 ms 36816 KB Expected int32, but "9069179206125513728" found
16 Incorrect 165 ms 39492 KB Expected int32, but "1077624591058923776" found
17 Incorrect 171 ms 46756 KB Expected int32, but "9078516102168694496" found
18 Incorrect 125 ms 31112 KB Expected int32, but "8603867276704155842" found
19 Incorrect 171 ms 50124 KB Expected int32, but "9168401195073447936" found
20 Incorrect 209 ms 51420 KB Expected int32, but "9205429944092974250" found