oj.uz

Submission #91910

# Submission time Handle Problem Language Result Execution time Memory
91910 2018-12-31T11:42:07 Z ngot23 trapezoid (balkan11_trapezoid) C++11
100 / 100
 126 ms 9376 KB 
#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);
    }
}

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=lower_bound(vt.begin(), vt.end(), a[i].F.F)-vt.begin()+1;
        a[i].S.F=lower_bound(vd.begin(), vd.end(), a[i].S.F)-vd.begin()+1;
        b[i*2-1]={a[i].F.F, a[i].S.F, 1, i};

        a[i].F.S=lower_bound(vt.begin(), vt.end(), a[i].F.S)-vt.begin()+1;
        a[i].S.S=lower_bound(vd.begin(), vd.end(), a[i].S.S)-vd.begin()+1;
        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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 1912 KB Output is correct
3 Correct 4 ms 1912 KB Output is correct
4 Correct 4 ms 2040 KB Output is correct
5 Correct 5 ms 2168 KB Output is correct
6 Correct 6 ms 2296 KB Output is correct
7 Correct 7 ms 2296 KB Output is correct
8 Correct 9 ms 2424 KB Output is correct
9 Correct 15 ms 2912 KB Output is correct
10 Correct 25 ms 3704 KB Output is correct
11 Correct 31 ms 3956 KB Output is correct
12 Correct 65 ms 5868 KB Output is correct
13 Correct 73 ms 6504 KB Output is correct
14 Correct 90 ms 7300 KB Output is correct
15 Correct 99 ms 7620 KB Output is correct
16 Correct 109 ms 7908 KB Output is correct
17 Correct 117 ms 8292 KB Output is correct
18 Correct 109 ms 8756 KB Output is correct
19 Correct 111 ms 8928 KB Output is correct
20 Correct 126 ms 9376 KB Output is correct