Submission #870166

#	Time	Username	Problem	Language	Result	Execution time	Memory
870166		watse	trapezoid (balkan11_trapezoid)	C++14	100 / 100	89 ms	18252 KiB

trapezoid

#include <bits/stdc++.h>
#define fi first
#define se second
#define tl fi.fi
#define tr fi.se
#define dl se.fi
#define dr se.se
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int NMAX = 5e5 + 5;
const ll inf = 1e9;
const int mod = 30013;
pair <ii,ii> a[NMAX];

ii bit[NMAX];
int n;
void update (int x, ii val){
    for (; x <= 2 * n; x += x & -x)
    if (bit[x].fi < val.fi)
        bit[x] = val;
    else 
    if (bit[x].fi == val.fi)
        bit[x].se = (bit[x].se + val.se) % mod;
}

ii get (int x){
    ii ans = {0,1};
    for (; x > 0; x -= x & -x)
    if (bit[x].fi > ans.fi)
        ans = bit[x];
    else if (bit[x].fi == ans.fi)
        ans.se = (ans.se + bit[x].se) % mod;
    return ans;
}

ii ret,res[NMAX];
vector <int> t,d;
int g[NMAX],u[NMAX];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].tl >> a[i].tr >> a[i].dl >> a[i].dr;
        t.pb(a[i].tl);
        t.pb(a[i].tr);
        d.pb(a[i].dl);
        d.pb(a[i].dr);
    }
    sort(t.begin(),t.end());
    sort(d.begin(),d.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    d.erase(unique(d.begin(),d.end()),d.end());
    for (int i = 1; i <= n; ++i){
        a[i].tl = lower_bound (t.begin(),t.end(),a[i].tl) - t.begin() + 1;
        a[i].tr = lower_bound (t.begin(),t.end(),a[i].tr) - t.begin() + 1;
        a[i].dl = lower_bound (d.begin(),d.end(),a[i].dl) - d.begin() + 1;
        a[i].dr = lower_bound (d.begin(),d.end(),a[i].dr) - d.begin() + 1;
        g[a[i].tl] = i;
        u[a[i].tr] = i;
    }
    for (int i = 1; i <= 2 * n; i++){
        if (g[i]){
            int v = g[i];
            ii f = get(a[v].dl);
            ++f.fi;
            res[v] = f;
            if (f.fi > ret.fi)
                ret = f;
            else if (f.fi == ret.fi)
                ret.se = (ret.se + f.se) % mod;
        }
        else {
            int v = u[i];
            update(a[v].dr,res[v]);
        }
    }
    cout << ret.fi << " " << ret.se;
    return 0;
}

• Subtask 1: 100 / 100