oj.uz

Submission #707786

# Submission time Handle Problem Language Result Execution time Memory
707786 2023-03-10T06:43:14 Z LittleOrange trapezoid (balkan11_trapezoid) C++17
40 / 100
 204 ms 48824 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 << " " << 1 << '\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;
      |                    ~^~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 0 ms 340 KB Partially correct
3 Partially correct 1 ms 468 KB Partially correct
4 Partially correct 1 ms 596 KB Partially correct
5 Partially correct 3 ms 1364 KB Partially correct
6 Partially correct 4 ms 2076 KB Partially correct
7 Partially correct 5 ms 1620 KB Partially correct
8 Partially correct 9 ms 2520 KB Partially correct
9 Partially correct 16 ms 5724 KB Partially correct
10 Partially correct 29 ms 6836 KB Partially correct
11 Partially correct 48 ms 13412 KB Partially correct
12 Partially correct 91 ms 27320 KB Partially correct
13 Partially correct 113 ms 31384 KB Partially correct
14 Partially correct 134 ms 38456 KB Partially correct
15 Partially correct 147 ms 34780 KB Partially correct
16 Partially correct 171 ms 37344 KB Partially correct
17 Partially correct 173 ms 44348 KB Partially correct
18 Partially correct 120 ms 28708 KB Partially correct
19 Partially correct 183 ms 47448 KB Partially correct
20 Partially correct 204 ms 48824 KB Partially correct