oj.uz

Submission #91895

# Submission time Handle Problem Language Result Execution time Memory
91895 2018-12-31T10:38:48 Z ngot23 trapezoid (balkan11_trapezoid) C++11
45 / 100
 500 ms 7380 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];

    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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 22 ms 808 KB Output is correct
7 Correct 35 ms 888 KB Output is correct
8 Correct 47 ms 1016 KB Output is correct
9 Correct 182 ms 1788 KB Output is correct
10 Execution timed out 852 ms 2960 KB Time limit exceeded
11 Execution timed out 1082 ms 2712 KB Time limit exceeded
12 Execution timed out 1079 ms 4076 KB Time limit exceeded
13 Execution timed out 1082 ms 4668 KB Time limit exceeded
14 Execution timed out 1077 ms 5540 KB Time limit exceeded
15 Execution timed out 1082 ms 5652 KB Time limit exceeded
16 Execution timed out 1082 ms 5984 KB Time limit exceeded
17 Execution timed out 1079 ms 6384 KB Time limit exceeded
18 Execution timed out 1083 ms 6612 KB Time limit exceeded
19 Execution timed out 1068 ms 6988 KB Time limit exceeded
20 Execution timed out 1086 ms 7380 KB Time limit exceeded