oj.uz

Submission #547605

# Submission time Handle Problem Language Result Execution time Memory
547605 2022-04-11T05:03:27 Z Soul234 trapezoid (balkan11_trapezoid) C++14
43 / 100
 103 ms 11284 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}


const int MOD = 30013;

int add(int a, int b) {
    if((a += b) >= MOD) a-=MOD;
    return a;
}

struct Tr {
    int a,b,c,d;
    bool operator<(const Tr& rhs) {
        return a < rhs.a;
    }
};

tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a = b, 1 : 0;
}

tcT> struct SegTree {
	const T ID = {0,0}; T cmb(const T&a, const T&b) {
	    if(a.first == b.first) return {a.first, add(a.second, b.second) };
	    return a.first > b.first ? a : b;
    }
	int n; V<T> seg;
	void init(int _n) {
		for (n = 1; n < _n; ) n *= 2;
		seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = cmb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) {
		ckmax(seg[p += n], val) ; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = cmb(ra,seg[l++]);
			if (r&1) rb = cmb(seg[--r],rb);
		}
		return cmb(ra,rb);
	}
};

const int MX = 1e5+5;
int N;
SegTree<pi> st;
vi compr;
V<Tr> tr;
pi ans[MX];
pi res = {0, 1};

void solve() {
    cin>>N;
    F0R(i,N) {
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        tr.pb({a,b,c,d});
        compr.pb(c); compr.pb(d);
    }
    sort(all(compr)); compr.erase(unique(all(compr)), compr.end());
    F0R(i,N) {
        tr[i].c = lower_bound(all(compr), tr[i].c) - compr.begin();
        tr[i].d = lower_bound(all(compr), tr[i].d) - compr.begin();
    }
    sort(all(tr));
    st.init(sz(compr));
    pqg<pi> pq;
    F0R(i,sz(tr)) {
        while(sz(pq) && pq.top().first <= tr[i].a) {
            int ind = pq.top().second;
            st.upd(tr[ind].d, ans[ind]);
            pq.pop();
        }
        pq.push({tr[i].b, i});
        pi tmp = st.query(0, tr[i].c-1);
        //dbg(tmp.first, tmp.second);
        if(tmp.first == 0) ans[i] = {1, 1};
        else ans[i] = {tmp.first+1, tmp.second};
        ckmax(res, ans[i]);
    }
    cout << res.first << " " << res.second << nl;
}

int main() {
    setIO();

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

    return 0;
}

Compilation message

trapezoid.cpp: In function 'void setIO(std::string)':
trapezoid.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 1 ms 332 KB Partially correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 468 KB Partially correct
5 Partially correct 2 ms 468 KB Partially correct
6 Partially correct 4 ms 596 KB Partially correct
7 Partially correct 4 ms 600 KB Partially correct
8 Partially correct 5 ms 852 KB Partially correct
9 Partially correct 10 ms 1508 KB Partially correct
10 Partially correct 19 ms 2768 KB Partially correct
11 Partially correct 24 ms 3016 KB Partially correct
12 Partially correct 49 ms 5812 KB Partially correct
13 Correct 58 ms 6340 KB Output is correct
14 Partially correct 71 ms 9636 KB Partially correct
15 Partially correct 83 ms 9708 KB Partially correct
16 Partially correct 92 ms 9992 KB Partially correct
17 Partially correct 90 ms 10408 KB Partially correct
18 Partially correct 86 ms 10656 KB Partially correct
19 Partially correct 92 ms 10916 KB Partially correct
20 Partially correct 103 ms 11284 KB Partially correct