Submission #361426

#	Time	Username	Problem	Language	Result	Execution time	Memory
361426		pure_mem	trapezoid (balkan11_trapezoid)	C++14	100 / 100	173 ms	11500 KiB

trapezoid

#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 3, MX = 1e7, INF = 1e9, mod = 30013;

int n, a[4][N], p[N * 2], lens;
pair<int, int> todo[N];
struct node{
	int L, R, dp, sum;
}t[MX];
int cur_sz = 1;
void upd(int v, int tl, int tr, int pos, pair<int, int> val){
	if(tl == tr){
		t[v].dp = val.X, t[v].sum = val.Y;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm){
		if(t[v].L == 0)
			t[v].L = ++cur_sz;
		upd(t[v].L, tl, tm, pos, val);
	}
	else{
	    if(t[v].R == 0)
	    	t[v].R = ++cur_sz;
	    upd(t[v].R, tm + 1, tr, pos, val);
	}
	t[v].dp = max(t[t[v].L].dp, t[t[v].R].dp), t[v].sum = 0;
	if(t[t[v].L].dp == t[v].dp)
		t[v].sum += t[t[v].L].sum;
	if(t[t[v].R].dp == t[v].dp)
		t[v].sum += t[t[v].R].sum;
	t[v].sum %= mod;	
}
pair<int, int> get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr || v == 0)
		return MP(0, 0);
	if(tl >= l && tr <= r)
		return MP(t[v].dp, t[v].sum);
	int tm = (tl + tr) / 2;
	pair<int, int> tmpL = get(t[v].L, tl, tm, l, r), tmpR = get(t[v].R, tm + 1, tr, l, r);
	if(tmpL.X < tmpR.X)
		return tmpR;
	if(tmpL.X == tmpR.X)
		tmpL.Y = (tmpL.Y + tmpR.Y) % mod;
	return tmpL;
}

int main () {
	scanf("%d", &n);
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < 4;j++)
			scanf("%d", &a[j][i]);
		p[++lens] = i, p[++lens] = -i;
	}
	sort(p + 1, p + lens + 1, [](int x, int y){
		int x1 = (x > 0? a[1][x]: a[0][-x]), y1 = (y > 0? a[1][y]: a[0][-y]);
		return x1 < y1;
	});
	for(int it = 1;it <= lens;it++){
		int v = p[it];
		if(v < 0){
			v = -v;
			pair<int, int> tmp = get(1, 1, INF, 1, a[2][v]);
			tmp.X += 1;
			if(tmp.X == 1)
				tmp.Y = 1;
			todo[v] = tmp;
		}
		else{
		    upd(1, 1, INF, a[3][v], todo[v]);
		}
	}
	printf("%d %d", t[1].dp, t[1].sum);
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100