Submission #707790

#	Time	Username	Problem	Language	Result	Execution time	Memory
707790		LittleOrange	trapezoid (balkan11_trapezoid)	C++17	43 / 100	208 ms	48636 KiB

trapezoid

#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 (stderr)

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 / 100