oj.uz

답안 #344146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344146 2021-01-05T07:48:22 Z pure_mem 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 172 ms 11048 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 5 ms 736 KB Output is correct
7 Correct 7 ms 812 KB Output is correct
8 Correct 8 ms 968 KB Output is correct
9 Correct 15 ms 1532 KB Output is correct
10 Correct 30 ms 2956 KB Output is correct
11 Correct 39 ms 2968 KB Output is correct
12 Correct 102 ms 5836 KB Output is correct
13 Correct 124 ms 6512 KB Output is correct
14 Correct 119 ms 9572 KB Output is correct
15 Correct 135 ms 9840 KB Output is correct
16 Correct 150 ms 10120 KB Output is correct
17 Correct 153 ms 10500 KB Output is correct
18 Correct 159 ms 10656 KB Output is correct
19 Correct 155 ms 10396 KB Output is correct
20 Correct 172 ms 11048 KB Output is correct