oj.uz

Submission #91907

# Submission time Handle Problem Language Result Execution time Memory
91907 2018-12-31T11:26:13 Z ngot23 trapezoid (balkan11_trapezoid) C++11
45 / 100
 500 ms 7284 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);
    }
}

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 4 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 5 ms 2040 KB Output is correct
5 Correct 9 ms 2172 KB Output is correct
6 Correct 23 ms 2296 KB Output is correct
7 Correct 37 ms 2296 KB Output is correct
8 Correct 49 ms 2512 KB Output is correct
9 Correct 176 ms 3036 KB Output is correct
10 Execution timed out 879 ms 4212 KB Time limit exceeded
11 Execution timed out 1083 ms 4212 KB Time limit exceeded
12 Execution timed out 1085 ms 5344 KB Time limit exceeded
13 Execution timed out 1083 ms 5780 KB Time limit exceeded
14 Execution timed out 1094 ms 5984 KB Time limit exceeded
15 Execution timed out 1082 ms 6244 KB Time limit exceeded
16 Execution timed out 1084 ms 6416 KB Time limit exceeded
17 Execution timed out 1085 ms 6852 KB Time limit exceeded
18 Execution timed out 1079 ms 6812 KB Time limit exceeded
19 Execution timed out 1082 ms 7036 KB Time limit exceeded
20 Execution timed out 1070 ms 7284 KB Time limit exceeded