oj.uz

Submission #707790

# Submission time Handle Problem Language Result Execution time Memory
707790 2023-03-10T06:46:52 Z LittleOrange trapezoid (balkan11_trapezoid) C++17
43 / 100
 208 ms 48636 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 30013;
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)%mod):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%mod) << '\n';
}

Compilation message

trapezoid.cpp: In member function 'void segtree::add(ll, ll, ll, ll, ll, obj)':
trapezoid.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |             ll m = l+r>>1;
      |                    ~^~
trapezoid.cpp: In member function 'obj segtree::query(ll, ll, ll, ll)':
trapezoid.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |             ll m = l+r>>1;
      |                    ~^~

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 1 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 4 ms 1364 KB Partially correct
6 Partially correct 5 ms 2060 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 6736 KB Partially correct
11 Partially correct 46 ms 13392 KB Partially correct
12 Partially correct 95 ms 27228 KB Partially correct
13 Correct 135 ms 31300 KB Output is correct
14 Partially correct 144 ms 38340 KB Partially correct
15 Partially correct 190 ms 34904 KB Partially correct
16 Partially correct 166 ms 37252 KB Partially correct
17 Partially correct 181 ms 44436 KB Partially correct
18 Partially correct 129 ms 28716 KB Partially correct
19 Partially correct 193 ms 47496 KB Partially correct
20 Partially correct 208 ms 48636 KB Partially correct