Submission #623010

#	Time	Username	Problem	Language	Result	Execution time	Memory
623010		zhangjishen	trapezoid (balkan11_trapezoid)	C++98	40 / 100	94 ms	9632 KiB

trapezoid

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

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

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

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 Op{
	int x, y, tp, i;
	friend bool operator<(const Op& a, const Op& b){
		return a.x < b.x;
	}
}op[MAXN * 2];
int n, a[MAXN], b[MAXN], c[MAXN], d[MAXN], f[MAXN];
int q, disc[MAXN * 2], tot;

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
	// disc
	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;
	}
	// sort op
	for(int i = 1; i <= n; i++){
		op[++q] = (Op){a[i], c[i], 2, i};
		op[++q] = (Op){b[i], d[i], 1, i};
	}
	sort(op + 1, op + q + 1);
	// dp
	siz = tot;
	for(int i = 1; i <= q; i++){
		if(op[i].tp == 1)
			upd(op[i].y, f[op[i].i]);
		else f[op[i].i] = ask(op[i].y) + 1;
	}
	// output
	int ans = 0;
	for(int i = 1; i <= n; i++)
		chkmax(ans, f[i]);
	printf("%d 0\n", ans);
}

Compilation message (stderr)

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

• Subtask 1: 40 / 100