Submission #344146

#	Time	Username	Problem	Language	Result	Execution time	Memory
344146		pure_mem	trapezoid (balkan11_trapezoid)	C++14	100 / 100	172 ms	11048 KiB

trapezoid

#include <bits/stdc++.h>

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

using namespace std;

const int N = 1e5 + 1;
const int mod = 30013;

pair<int, int> t[N * 8], dp[N];
void upd(int v, int tl, int tr, int pos, pair<int, int> val){
	if(tl > pos || pos > tr)
		return;
	if(tl == tr)
		return void(t[v] = val);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, pos, val);
	upd(v * 2 + 1, tm + 1, tr, pos, val);
	if(t[v * 2].X > t[v * 2 + 1].X)
		t[v] = t[v * 2];
	else if(t[v * 2].X < t[v * 2 + 1].X)
		t[v] = t[v * 2 + 1];
	else
		t[v] = MP(t[v * 2].X, (t[v * 2].Y + t[v * 2 + 1].Y) % mod);
}
pair<int, int> get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return MP(0, 0);
	if(tl >= l && tr <= r)
		return t[v];
    int tm = (tl + tr) / 2;
    pair<int, int> left = get(v * 2, tl, tm, l, r), right = get(v * 2 + 1, tm + 1, tr, l, r);
    if(left.X > right.X)
    	return left;
    else if(left.X < right.X)
    	return right;
    else
    	return MP(left.X, (left.Y + right.Y) % mod);
}    
int a[4][N], n, m;                                     
void shrink(){
	vector< pair< int, pair<int, int> > > tmp;
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
		for(int j = 0;j < 4;j++){
			scanf("%d", &a[j][i]); 
			if(j > 1)
				tmp.push_back(MP(a[j][i], MP(j, i)));
	    }
	sort(tmp.begin(), tmp.end());
	for(int i = 0;i < 2 * n;i++){
		if(i == 0 || tmp[i - 1].X != tmp[i].X)
			m++;
		a[tmp[i].Y.X][tmp[i].Y.Y] = m;	
	}
}                              

int main () {
	shrink();
	vector<int> tmp;
	int len = 0, ans = 0;
	for(int i = 1;i <= n;i++)
		tmp.push_back(i), tmp.push_back(-i);
	sort(tmp.begin(), tmp.end(), [](int x, int y){
		x = x > 0?a[1][x]:a[0][-x];
		y = y > 0?a[1][y]:a[0][-y];
		return x < y;
	});
	for(int v: tmp){
		if(v < 0){
			v = -v;
			dp[v] = get(1, 1, m, 1, a[2][v]);
			dp[v].X += 1;
			if(dp[v].X == 1)
				dp[v].Y += 1;
			if(dp[v].X > len)
				len = dp[v].X, ans = dp[v].Y;
			else if(dp[v].X == len)
				ans = (ans + dp[v].Y) % mod;
		}
		else{
		    upd(1, 1, m, a[3][v], dp[v]);
		}		
	}
	printf("%d %d", len, ans);
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100