Submission #624366

#	Time	Username	Problem	Language	Result	Execution time	Memory
624366		zhangjishen	trapezoid (balkan11_trapezoid)	C++98	100 / 100	112 ms	10300 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
const int MAXN = 1e5 + 10, mod = 30013;

// BIT
struct BIT_max{
	int bit[MAXN * 2], siz;

	BIT_max(int n){
		siz = n;
		memset(bit, 0, sizeof(bit));
	}

	int lsb(int i){
		return i & -i;
	}

	void upd(int i, int k){
		for(; i <= siz; i += lsb(i))
			chkmax(bit[i], k);
	}

	int ask(int i){
		int ans = 0;
		for(; i; i -= lsb(i))
			chkmax(ans, bit[i]);
		return ans;
	}
};

struct BIT_sum{
	int bit[MAXN * 2], siz;

	BIT_sum(int n){
		siz = n;
		memset(bit, 0, sizeof(bit));
	}

	int lsb(int i){
		return i & -i;
	}

	void add(int i, int k){
		for(; i <= siz; i += lsb(i))
			(bit[i] += k) %= mod;
	}

	int ask(int i){
		int ans = 0;
		for(; i; i -= lsb(i))
			(ans += bit[i]) %= mod;
		return (ans + mod) % mod;
	}
};

struct Op{
	int x, y, tp, i;
	friend bool operator<(const Op& a, const Op& b){
		return a.x < b.x;
	}
};

int tot, disc[MAXN * 2];
void Disc(int n, int c[], int d[]){
	tot = 0;
	for(int i = 1; i <= n; i++)
		disc[++tot] = c[i], disc[++tot] = d[i];
	sort(disc + 1, disc + tot + 1);
	tot = unique(disc + 1, disc + tot + 1) - disc - 1;
	for(int i = 1; i <= n; i++){
		c[i] = lower_bound(disc + 1, disc + tot + 1, c[i]) - disc;
		d[i] = lower_bound(disc + 1, disc + tot + 1, d[i]) - disc;
	}
}

int dp_f(int n, int a[], int b[], int c[], int d[], int f[]){
	// sort op
	vector<Op> op;
	for(int i = 1; i <= n; i++){
		op.pb((Op){a[i], c[i], 2, i});
		op.pb((Op){b[i], d[i], 1, i});
	}
	sort(op.begin(), op.end());
	// dp f
	BIT_max y(tot);	// y[i]: max f at y = i
	for(int i = 0; i < (int)op.size(); i++){
		if(op[i].tp == 1)
			y.upd(op[i].y, f[op[i].i]);
		else f[op[i].i] = y.ask(op[i].y) + 1;
	}
	// ans
	int ans = 0;
	for(int i = 1; i <= n; i++)
		chkmax(ans, f[i]);
	return ans;
}

int dp_g(int n, int a[], int b[], int c[], int d[], int f[], int g[], int len){
	vector<int> tpz[MAXN];	// catagorize trapezoid with f = 1 ~ len
	for(int i = 1; i <= n; i++)
		tpz[f[i]].pb(i);
	// dp g
	for(int i = 0; i < (int)tpz[1].size(); i++)	// init
		g[tpz[1][i]] = 1;

	vector<Op> op;	
	BIT_sum y(tot);
	for(int k = 2; k <= len; k++){
		op.clear();
		for(int i = 0; i < (int)tpz[k - 1].size(); i++){
			int j = tpz[k - 1][i];
			op.pb((Op){b[j], d[j], 1, j});
		}
		for(int i = 0; i < (int)tpz[k].size(); i++){
			int j = tpz[k][i];
			op.pb((Op){a[j], c[j], 2, j});
		}
		sort(op.begin(), op.end());

		for(int i = 0; i < (int)op.size(); i++){
			if(op[i].tp == 1)
				y.add(op[i].y, g[op[i].i]);
			else g[op[i].i] = y.ask(op[i].y);
		}

		// undo BIT in linear time
		for(int i = 0; i < (int)op.size(); i++)
			if(op[i].tp == 1)
				y.add(op[i].y, -g[op[i].i]);
	}

	int ans = 0;
	for(int i = 1; i <= n; i++)
		if(f[i] == len)
			(ans += g[i]) %= mod;
	return ans;
}

int n, a[MAXN], b[MAXN], c[MAXN], d[MAXN], f[MAXN], g[MAXN], ans1, ans2;
int main(){
	// input
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
	// disc
	Disc(n, c, d);
	ans1 = dp_f(n, a, b, c, d, f);
	ans2 = dp_g(n, a, b, c, d, f, g, ans1);
	printf("%d %d\n", ans1, ans2);
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
trapezoid.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100