Submission #547606

#	Time	Username	Problem	Language	Result	Execution time	Memory
547606		Soul234	trapezoid (balkan11_trapezoid)	C++14	100 / 100	99 ms	9044 KiB

trapezoid

#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;
const int INF = 1e9+7;

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);
    }
    N++;
    tr.pb({INF-1, INF, INF-1, INF});
    compr.pb(INF-1); compr.pb(INF);
    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};
    }
    cout << ans[sz(tr)-1].first-1 << " " << ans[sz(tr)-1].second << nl;
}

int main() {
    setIO();

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

    return 0;
}

Compilation message (stderr)

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: 100 / 100