oj.uz

Submission #708111

# Submission time Handle Problem Language Result Execution time Memory
708111 2023-03-11T05:38:22 Z swagchicken trapezoid (balkan11_trapezoid) C++14
40 / 100
 356 ms 48708 KB 
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  = 998244353;
#define inf 1e18;
#define INF INT_MAX

long double PI = 4*atan(1);
long double eps = 1e-12;


template<class T>
class SegmentTree {
    private:
        int n;
        vector<T> A, st;

    int l(int p) { return 2*p; }
    int r(int p) { return 2*p+1; }

    T conquer(T a, T b) {
        if (a == -1) return b;  // only useful for range min/max queries?  
        if (b == -1) return a;
        return max(a,b);
    }

    void build(int p, int L, int R) {
        if (L == R) {
            st[p] = A[L];
        } else {
            int m = (L + R)/2;
            build(l(p), L, m);
            build(r(p), m+1, R);
            st[p] = conquer(st[l(p)], st[r(p)]);
        }
    }

    T RMQ(int p, int L, int R, int ql, int qr) {   // O(log n)
        if(qr < L || R < ql) return -1;                      // infeasible
        if ((ql <= L) && (R <= qr)) return st[p];      // found the segment
        int m = (L+R)/2;
        return conquer(RMQ(l(p), L  , m, ql, qr),
                       RMQ(r(p), m+1, R, ql, qr));
    }

    void update(int p, int L, int R, int i, T val) {
        if (L == R) {
            st[p] = val;
            return;
        }
        int m = (L + R)/2;
        if (i <= m)
            update(l(p), L, m, i, val);
        else
            update(r(p), m+1, R, i, val);
        st[p] = conquer(st[l(p)], st[r(p)]);
    }


    public:
        SegmentTree(int sz) : n(sz), st(4*n) {}

        SegmentTree(const vector<T> &initialA) : SegmentTree((int) initialA.size()) {
            A = initialA;
            build(1,0,n-1);
        }

        void update(int i, T val) {
            update(1,0,n-1,i,val);
        }

        T RMQ(int i, int j) {
            return RMQ(1,0,n-1,i,j);
        }

};


vector<pii> queries(210000, {-1e9, -1});
vector<pii> updates(210000, {-1e9, -1});

int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    #ifdef DEBUG
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif  

    int n; cin >> n;
    vector<piiii> trap(n);
    set<int> topv, botv;
    map<int, int> topcmp;
    map<int, int> botcmp;
    FOR(i,0,n) {
      cin >> trap[i].ff.ff >> trap[i].ff.ss >> trap[i].ss.ff >> trap[i].ss.ss;
      
      topv.insert(trap[i].ff.ff); 
      topv.insert(trap[i].ff.ss);

      botv.insert(trap[i].ss.ff);
      botv.insert(trap[i].ss.ss);
    }

    int cnt = 0;
    for(int v : topv) {
      topcmp[v] = cnt; cnt++;
    }
    cnt = 0;
    for(int v : botv) {
      botcmp[v] = cnt; cnt++;
    }

    FOR(i,0,n) {
      queries[topcmp[trap[i].ff.ff]] = {botcmp[trap[i].ss.ff], i};
    }
    
    SegmentTree<int> st(210000);


    FOR(i,0,210000) {
      if(queries[i].ff != -1e9) {
        int curr = st.RMQ(0,queries[i].ff) + 1;
        int idx = queries[i].ss;
        updates[topcmp[trap[idx].ff.ss]] = {curr , idx};
      }
      if(updates[i].ff != -1e9) {
        int idx = updates[i].ss;
        int curr = updates[i].ff;
        st.update(botcmp[trap[idx].ss.ss], curr);
      }
    }

    int ans = st.RMQ(0,210000);
    cout << ans << " " << -1 << endl;


    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 6868 KB Partially correct
2 Partially correct 6 ms 6868 KB Partially correct
3 Partially correct 5 ms 6996 KB Partially correct
4 Partially correct 5 ms 7252 KB Partially correct
5 Partially correct 7 ms 7616 KB Partially correct
6 Partially correct 9 ms 8112 KB Partially correct
7 Partially correct 12 ms 8532 KB Partially correct
8 Partially correct 16 ms 8916 KB Partially correct
9 Partially correct 30 ms 10956 KB Partially correct
10 Partially correct 58 ms 15168 KB Partially correct
11 Partially correct 73 ms 17308 KB Partially correct
12 Partially correct 175 ms 27800 KB Partially correct
13 Partially correct 206 ms 32172 KB Partially correct
14 Partially correct 267 ms 36228 KB Partially correct
15 Partially correct 290 ms 38220 KB Partially correct
16 Partially correct 316 ms 40320 KB Partially correct
17 Partially correct 311 ms 42444 KB Partially correct
18 Partially correct 287 ms 44552 KB Partially correct
19 Partially correct 322 ms 46668 KB Partially correct
20 Partially correct 356 ms 48708 KB Partially correct