Submission #91907

#	Time	Username	Problem	Language	Result	Execution time	Memory
91907		ngot23	trapezoid (balkan11_trapezoid)	C++11	45 / 100	1094 ms	7284 KiB

trapezoid

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define mp make_pair
#define PB push_back
#define pii pair<int,int>
#define F first
#define S second
#define Task "trapeze"
using namespace std;
const int N=100005;
const int mod=30013;
struct data {
    int rr, val, type, id;
    bool operator < (const data &X) const {
        return (rr<X.rr)||((rr==X.rr)&&(type>X.type));
    }
} b[N*2];
int n;
pair <pii, pii > a[N];
vector <int > vt, vd;
pii dp[N], ans;

pii MAX(pii A, pii B) {
        if(A.F>B.F) return A;
        if(A.F<B.F) return B;
        A.S=(A.S+B.S)%mod;
        return A;
}

struct fenwicktree {
    pii t[N*2];

    fenwicktree() {
        rep(i, 0, N*2-1) t[i]=mp(0, 0);
    }
    void update(int node, pii X) {
        while(node<=n*2) {
            t[node]=MAX(t[node], X);
            node+=node&(-node);
        }
    }

    pii get(int node) {
        pii ret=mp(0, 0);
        while(node>0) {
            ret=MAX(ret, t[node]);
            node-=node&(-node);
        }
        return ret;
    }
} BIT;

void setup() {
    cin >> n;
    rep(i, 1, n) {
        cin >> a[i].F.F >> a[i].F.S >> a[i].S.F >> a[i].S.S;
        vt.PB(a[i].F.F); vt.PB(a[i].F.S);
        vd.PB(a[i].S.F); vd.PB(a[i].S.S);
    }
}

int Find(vector <int > v, int val) {
    int id=lower_bound(v.begin(), v.end(), val)-v.begin()+1;
    return id;
}

void pre() {
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end())-vt.begin());
    sort(vd.begin(), vd.end());
    vd.resize(unique(vd.begin(), vd.end())-vd.begin());

    rep(i, 1, n) {
        a[i].F.F=Find(vt, a[i].F.F);
        a[i].S.F=Find(vd, a[i].S.F);
        b[i*2-1]={a[i].F.F, a[i].S.F, 1, i};

        a[i].F.S=Find(vt, a[i].F.S);
        a[i].S.S=Find(vd, a[i].S.S);
        b[i*2]={a[i].F.S, a[i].S.S, -1, i};
    }
    sort(b+1, b+n*2+1);
}

void calc() {
    rep(i, 1, n*2) {
        if(b[i].type==1) {
            int id=b[i].id;
            pii prv=BIT.get(b[i].val-1);
            dp[id]=mp(prv.F+1, prv.S);
            if(dp[id].F==1) dp[id].S=1;
            ans=MAX(ans, dp[id]);
        } else {
            int id=b[i].id;
            BIT.update(b[i].val, dp[id]);
        }
    }
    cout << ans.F << ' ' << ans.S;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   // freopen(Task".inp", "r", stdin);
  //  freopen(Task".out", "w", stdout);
    setup();
    pre();
    calc();
    return 0;
}

• Subtask 1: 45 / 100