oj.uz

Submission #231139

# Submission time Handle Problem Language Result Execution time Memory
231139 2020-05-12T21:20:23 Z summitwei trapezoid (balkan11_trapezoid) C++17
100 / 100
 464 ms 24568 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define INF 0x3f3f3f3f
#define MOD 30013
#define f first
#define s second
#define pb push_back

#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define F0R(i, a) for(int i=0; i<a; ++i)

#define MN 100005
int n;
pair<pii, pii> a[MN];

pii tree[MN*2];
pii merge(pii a, pii b){
    if(a.f != b.f) return max(a, b);
    else return {a.f, (a.s+b.s)%MOD};
}
void upd(int x, pii res){
    while(x <= 2*n){
        tree[x] = merge(tree[x], res);
        x += (x&-x);
    }
}
pii que(int x){
    pii ans = {0, 0};
    while(x >= 1){
        ans = merge(ans, tree[x]);
        x -= (x&-x);
    }
    return ans;
}

pii bruh[MN*2]; //index, change

map<int, int> top, bot;
pii dp[MN];
int main(){
    cin >> n;
    F0R(i, n){
        cin >> a[i].f.f >> a[i].f.s >> a[i].s.f >> a[i].s.s;
        top[a[i].f.f] = top[a[i].f.s] = bot[a[i].s.f] = bot[a[i].s.s] = 0;
    }
    int t = 0;
    for(auto &u : top) u.s = ++t;
    t = 0;
    for(auto &u : bot) u.s = ++t;
    F0R(i, n){
        a[i].f.f = top[a[i].f.f];
        a[i].f.s = top[a[i].f.s];
        a[i].s.f = bot[a[i].s.f];
        a[i].s.s = bot[a[i].s.s];
        bruh[a[i].f.f] = {i, 0};
        bruh[a[i].f.s] = {i, 1};
        //cout << a[i].f.f << " " << a[i].f.s << " " << a[i].s.f << " " << a[i].s.s << "\n";
    }
    FOR(i, 1, 2*n){
        int j = bruh[i].f;
        if(bruh[i].s){
            //include
            upd(a[j].s.s, dp[j]);
            //cout << "upd " << j+1 << " " << a[j].s.s << " " << dp[j].f << " " << dp[j].s << "\n";
        } else{
            //cout << "que " << a[j].s.f << "\n";
            pii res = que(a[j].s.f);
            res.f++;
            if(res.s == 0) res.s=1;
            dp[j] = res;
            //cout << j+1 << " has " << res.f << " " << res.s << "\n";
        }
    }
    pii ans = {0, 0};
    F0R(i, n){
        ans = merge(ans, dp[i]);
    }
    cout << ans.f << " " << ans.s << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 13 ms 1024 KB Output is correct
7 Correct 16 ms 1280 KB Output is correct
8 Correct 20 ms 1588 KB Output is correct
9 Correct 36 ms 2808 KB Output is correct
10 Correct 73 ms 5192 KB Output is correct
11 Correct 96 ms 6392 KB Output is correct
12 Correct 215 ms 12512 KB Output is correct
13 Correct 261 ms 14840 KB Output is correct
14 Correct 327 ms 17528 KB Output is correct
15 Correct 406 ms 18552 KB Output is correct
16 Correct 408 ms 19960 KB Output is correct
17 Correct 413 ms 20984 KB Output is correct
18 Correct 355 ms 22140 KB Output is correct
19 Correct 414 ms 23288 KB Output is correct
20 Correct 464 ms 24568 KB Output is correct