oj.uz

Submission #361426

# Submission time Handle Problem Language Result Execution time Memory
361426 2021-01-30T03:35:24 Z pure_mem trapezoid (balkan11_trapezoid) C++14
100 / 100
 173 ms 11500 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 4 ms 620 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 8 ms 748 KB Output is correct
9 Correct 17 ms 1388 KB Output is correct
10 Correct 40 ms 3052 KB Output is correct
11 Correct 39 ms 3180 KB Output is correct
12 Correct 93 ms 6636 KB Output is correct
13 Correct 109 ms 7836 KB Output is correct
14 Correct 142 ms 10220 KB Output is correct
15 Correct 137 ms 8556 KB Output is correct
16 Correct 147 ms 9580 KB Output is correct
17 Correct 152 ms 10988 KB Output is correct
18 Correct 148 ms 9964 KB Output is correct
19 Correct 146 ms 10732 KB Output is correct
20 Correct 173 ms 11500 KB Output is correct