oj.uz

Submission #707789

# Submission time Handle Problem Language Result Execution time Memory
707789 2023-03-10T06:45:11 Z LittleOrange trapezoid (balkan11_trapezoid) C++17
43 / 100
 202 ms 48684 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)%30013):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;
      |                    ~^~

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 232 KB Partially correct
2 Partially correct 1 ms 340 KB Partially correct
3 Partially correct 1 ms 468 KB Partially correct
4 Partially correct 2 ms 596 KB Partially correct
5 Partially correct 3 ms 1364 KB Partially correct
6 Partially correct 5 ms 2004 KB Partially correct
7 Partially correct 5 ms 1620 KB Partially correct
8 Partially correct 8 ms 2520 KB Partially correct
9 Partially correct 17 ms 5716 KB Partially correct
10 Partially correct 27 ms 6720 KB Partially correct
11 Partially correct 46 ms 13384 KB Partially correct
12 Partially correct 95 ms 27320 KB Partially correct
13 Correct 144 ms 31340 KB Output is correct
14 Partially correct 152 ms 38596 KB Partially correct
15 Partially correct 155 ms 34712 KB Partially correct
16 Partially correct 171 ms 37308 KB Partially correct
17 Partially correct 180 ms 44552 KB Partially correct
18 Partially correct 140 ms 28752 KB Partially correct
19 Partially correct 194 ms 47448 KB Partially correct
20 Partially correct 202 ms 48684 KB Partially correct