Submission #887521

# Submission time Handle Problem Language Result Execution time Memory
887521 2023-12-14T16:58:25 Z nnhzzz trapezoid (balkan11_trapezoid) C++17
100 / 100
69 ms 15492 KB
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <locale>
#include <map>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
#include <chrono>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  (((i)>>(j))&1LL)
#define           MASK(i)  (1LL<<(i))
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define             vvpii  vector<vpii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
#define              endl  "\n"
#define                MP  make_pair
// #define               int  ll

//-----------------------------------------------------------------------------------------------//
int readInt(){
    char c;
    do{ c = getchar(); }while(c!='-' && !isdigit(c));
    bool neg = (c=='-');
    int res = neg?0:c-'0';
    while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
    return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const  ll   LINF = 1e18;
const int    INF = 1e9;
const int    LOG = 20;
const int   MAXN = 5e5+7;
const int      N = 1e2+3;
const int    MOD = 30013;
const int   BASE = 1e5;
const  ld    EPS = 1e-9;
const  ld     PI = acos(-1);
const int OFFSET = 1e3;
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

struct Node{
	int x,y,u,v;

	bool operator < (const Node &other) const {
		return x<other.x;
	}
};

struct FENWICK_TREE{
    vi f;
    int n;

    void update(int id, int val){
        for(; id<=n; id+=id&-id){
            f[id] += val;
        }
    }

    int get(int id){
        int res = 0;
        for(; id>0; id-=id&-id){
            res += f[id];
        }
        return res;
    }

    int get(int l, int r){
        return get(r)-get(l-1);
    }

    FENWICK_TREE(int _):n(_){
        f.resize(n+1);
    }
};

Node a[MAXN];
pii dp[MAXN];
int n;

namespace sub1{
	void solve(){
		int res1 = 0,res2 = 0;
		REP(i,1,n){
			dp[i] = MP(1,1);
			int dem = 0;
			REP(j,1,i-1){
				if(a[i].x>a[j].y && a[i].u>a[j].v){
					++dem;
					if(dp[j].fi>=dp[i].fi) dp[i] = MP(dp[j].fi+1,dp[j].se);
					else if(dp[i].fi==dp[j].fi+1) dp[i].se = (dp[i].se+dp[j].se)%MOD;
				}
			}
			maxi(res1,dp[i].fi);
			cerr << dem;
		}
		REP(i,1,n) if(dp[i].fi==res1) res2 = (res2+dp[i].se)%MOD;
		cout << res1 << " " << res2;
	}
}

namespace sub2{
	struct events{
		int fi,se,op,id;

		bool operator < (const events &other) const {
			return fi<other.fi;
		}
	};
	int b[MAXN];
	pii f[MAXN];
	const int BASE = MAXN-7;

	pii combine(const pii &u, const pii &v){
		if(u.fi<v.fi) return v;
		if(v.fi<u.fi) return u;
		return MP(u.fi,(u.se+v.se)%MOD);
	}

	void update(int id, pii val){
		for(; id<=BASE; id+=id&-id) f[id] = combine(f[id],val);
	}

	pii get(int id){
		pii res = MP(0,1);
		for(; id>0; id-=id&-id) res = combine(res,f[id]);
		return res;
	}

	void solve(){
		vector<events> ev;
		vi cur;
		REP(i,1,n){
			ev.push_back({a[i].x,a[i].u,-1,i});
			ev.push_back({a[i].y,a[i].v,1,i});
			cur.push_back(a[i].u); cur.push_back(a[i].v);
		}
		sort(ALL(cur)); cur.resize(unique(ALL(cur))-cur.begin());
		sort(ALL(ev));
		pii res = MP(1,1);
		REP(i,0,SZ(ev)-1){
			int fi = ev[i].fi,se = ev[i].se,op = ev[i].op,id = ev[i].id;
			int pos = upper_bound(ALL(cur),se)-cur.begin();
			if(op==-1){
				dp[id] = get(pos);
				++dp[id].fi;
				res = combine(res,dp[id]);
			}else{
				update(pos,dp[id]);
			}
		}
		cout << res.fi << " " << res.se;
	}

	// void solve(){
	// 	pii res = MP(1,1);
	// 	vpii cur; vi comp;
	// 	REP(i,1,n){
	// 		cur.push_back(MP(a[i].x,a[i].u));
	// 		// cur.push_back(MP(a[i].y,a[i].v));
	// 		comp.push_back(a[i].v);
	// 		comp.push_back(a[i].u);
	// 	}
	// 	sort(ALL(cur)); cur.resize(unique(ALL(cur))-cur.begin());
	// 	sort(ALL(comp)); comp.resize(unique(ALL(comp))-comp.begin());
	// 	FENWICK_TREE fen(MAXN-1);
	// 	priority_queue<pii,vpii,greater<pii>> heap;
	// 	REP(i,1,n){
	// 		heap.push(MP(a[i].y,a[i].v));
	// 		while(SZ(heap)!=0 && heap.top().fi<a[i].x){
	// 			int pos = upper_bound(ALL(comp),heap.top().se)-comp.begin();
	// 			fen.update(pos,1);
	// 			heap.pop();
	// 		}
	// 		int pos = upper_bound(ALL(comp),a[i].u)-comp.begin();
	// 		b[i] = fen.get(pos);
	// 	}
	// 	REP(i,1,n){
	// 		int l = b[i];
	// 		int r = upper_bound(ALL(cur),MP(a[i].x,a[i].u))-cur.begin();
	// 		dp[i] = get(l-1); ++dp[i].fi;
	// 		update(r,dp[i]);
	// 		cout << dp[i].fi << " " << dp[i].se << endl;
	// 		maxi(res,dp[i]);
	// 	}
	// 	res = get(2*n);
	// 	cout << res.fi << " " << res.se;
	// }
}

void solve(){
	n = readInt();
	REP(i,1,n){
		//cin >> a[i].x >> a[i].y >> a[i].u >> a[i].v;
		a[i].x = readInt();
		a[i].y = readInt();
		a[i].u = readInt();
		a[i].v = readInt();
	}
	sort(a+1,a+n+1);
	sub2::solve(); return ;
	if(n<=5000){
		sub1::solve();
		return ;
	}
	sub2::solve();
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    #define task1 "nnhzzz"
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

trapezoid.cpp: In function 'void sub2::solve()':
trapezoid.cpp:48:28: warning: unused variable 'first' [-Wunused-variable]
   48 | #define                fi  first
      |                            ^~~~~
trapezoid.cpp:201:8: note: in expansion of macro 'fi'
  201 |    int fi = ev[i].fi,se = ev[i].se,op = ev[i].op,id = ev[i].id;
      |        ^~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:274:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:275:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  275 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:279:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  279 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:280:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  280 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 7 ms 5148 KB Output is correct
10 Correct 11 ms 5908 KB Output is correct
11 Correct 15 ms 6164 KB Output is correct
12 Correct 35 ms 9864 KB Output is correct
13 Correct 38 ms 12292 KB Output is correct
14 Correct 46 ms 15104 KB Output is correct
15 Correct 52 ms 13940 KB Output is correct
16 Correct 57 ms 15492 KB Output is correct
17 Correct 57 ms 14328 KB Output is correct
18 Correct 47 ms 14584 KB Output is correct
19 Correct 57 ms 14940 KB Output is correct
20 Correct 69 ms 15008 KB Output is correct