oj.uz

Submission #526848

# Submission time Handle Problem Language Result Execution time Memory
526848 2022-02-16T09:50:45 Z BackNoob trapezoid (balkan11_trapezoid) C++14
43 / 100
 118 ms 10188 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 2e5 + 227;
const int inf = 1e9 + 277;
const int mod = 30013;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(ll l , ll r) {
    return l + rd() * 1LL * rd() % (r - l + 1);
}

struct item {
    int x, y, u, v;
} a[mxN];

struct SEG
{
    int l, r, ok , idx;
    bool operator<(const SEG &a) const
    {
        return l < a.l;
    }
};

int n;
int f[mxN];
int g[mxN];

void add(int &a , int b)
{
    a += b;
    if(a >= mod) a -= mod;
}

int bitmax[mxN * 4];
void updatemax(int pos, int val)
{
    for(; pos <= n * 4 ; pos += pos & -pos) maximize(bitmax[pos] , val);
}
int getmax(int pos)
{
    int res = 0;
    for(; pos > 0 ; pos -= pos & -pos) maximize(res , bitmax[pos]);
    return res;
}

vector<int> cp;
bool vis[mxN];

void solve()
{
//    n = Rand(2 , 3);
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i].x >> a[i].u >> a[i].y >> a[i].v;
//        a[i].x = Rand(1 , 10);
//        a[i].y = Rand(1 , 10);
//        a[i].u = Rand(a[i].x , 20);
//        a[i].v = Rand(a[i].y , 20);
        cp.pb(a[i].x);
        cp.pb(a[i].y);
        cp.pb(a[i].u);
        cp.pb(a[i].v);
    }

    //cout << n << endl;
    //for(int i = 1 ; i <= n ; i++)
    //    cout << a[i].x << ' ' << a[i].u << ' ' << a[i].y << ' ' << a[i].v << endl;

    sort(all(cp));
    cp.erase(unique(all(cp)) , cp.end());

    for(int i = 1 ; i <= n ; i++) {
        a[i].x = lower_bound(all(cp) , a[i].x) - cp.begin() + 1;
        a[i].y = lower_bound(all(cp) , a[i].y) - cp.begin() + 1;
        a[i].u = lower_bound(all(cp) , a[i].u) - cp.begin() + 1;
        a[i].v = lower_bound(all(cp) , a[i].v) - cp.begin() + 1;
    }


    vector<SEG> val;
    for(int i = 1 ; i <= n ; i++)
    {
        int x = a[i].x;
        int y = a[i].y;
        int u = a[i].u;
        int v = a[i].v;
        val.pb({x , y , 1 , i});
        //cout << val.back().idx << endl;
        val.pb({u , v , 0 , i});
        //cout << val.back().idx << endl;
    }
    sort(all(val));

//    for(int i = 0 ; i < sz(val) ; i++) {
//        auto it = val[i];
//        if(it.ok == 0) {
//            if(vis[it.idx] == false) {
//                cout << it.l << ' ' << it.r << ' ' << it.ok << ' ' << it.idx << endl;
//                cout << a[it.idx].x << ' ' << a[it.idx].y << ' ' << a[it.idx].u << ' ' << a[it.idx].v << endl;
//                cout << "f";
//                exit(0);
//            }
//        }
//        else {
//            vis[it.idx] = true;
//        }
//    }

    for(auto it : val)
    {
        int i = it.idx;
        if(it.ok == 0) {
            //cout << it.r << ' ' << f[i] << ' ' << g[i] << endl;
            updatemax(it.r , f[i]);
        }
        else {
            f[i] = max(1 , getmax(it.r - 1) + 1);
            if(f[i] == 1) add(g[f[i]] , 1);
            else add(g[f[i]] , g[f[i] - 1]);
        }
    }

    int res = getmax(4 * n);
    int ans = g[res];
    cout << res << ' ' << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--)
    {
        solve();
    }
    return 0;
}

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Partially correct 1 ms 328 KB Partially correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 588 KB Partially correct
5 Partially correct 2 ms 588 KB Partially correct
6 Partially correct 3 ms 716 KB Partially correct
7 Partially correct 5 ms 844 KB Partially correct
8 Partially correct 6 ms 972 KB Partially correct
9 Partially correct 11 ms 1484 KB Partially correct
10 Partially correct 20 ms 2636 KB Partially correct
11 Partially correct 26 ms 3068 KB Partially correct
12 Partially correct 56 ms 5264 KB Partially correct
13 Partially correct 72 ms 6428 KB Partially correct
14 Partially correct 87 ms 8072 KB Partially correct
15 Partially correct 91 ms 8308 KB Partially correct
16 Partially correct 106 ms 8664 KB Partially correct
17 Partially correct 102 ms 9016 KB Partially correct
18 Partially correct 99 ms 9104 KB Partially correct
19 Partially correct 115 ms 9728 KB Partially correct
20 Partially correct 118 ms 10188 KB Partially correct