oj.uz

답안 #361427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361427 2021-01-30T04:28:23 Z pure_mem Zoltan (COCI16_zoltan) C++14
140 / 140
 121 ms 12620 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 = 2e5 + 3, mod = 1e9 + 7;

int n, a[N], all;
pair<int, ll> fw[N], dp1[N], dp2[N];

inline void upd(int v, pair<int, ll> val){
	for(;v <= all;v |= v + 1){
		if(fw[v].X < val.X)
			fw[v] = val;
		else if(fw[v].X == val.X)
			fw[v].Y = (fw[v].Y + val.Y) % mod;
	}
}

inline pair<int, ll> get(int v){
	pair<int, ll> val = MP(0, 1);
	for(;v >= 0;v = (v & (v + 1)) - 1){
		if(fw[v].X > val.X)
			val = fw[v];
		else if(fw[v].X == val.X)
			val.Y = (fw[v].Y + val.Y) % mod;
	}
	return val;
}

inline void squiz(){
	vector< pair<int, int> > tmp;
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
		scanf("%d", a + i), tmp.push_back(MP(a[i], i));
	sort(tmp.begin(), tmp.end());
	for(int i = 0;i < (int)tmp.size();i++){
		if(i == 0 || tmp[i].X != tmp[i - 1].X)
			all++;
		a[tmp[i].Y] = all;
	}
}

int main () {
	squiz();
	for(int i = n;i >= 1;i--){
		dp1[i] = get(a[i] - 1), dp1[i].X += 1;
		if(dp1[i].X == 1)
			dp1[i].Y = 1;
		upd(a[i], dp1[i]);
	}
	memset(fw, 0, sizeof(fw));
	ll ans = 1;
	int mx = 0;
	for(int i = n;i >= 1;i--){
		dp2[i] = get(all - a[i]), dp2[i].X += 1;
		if(dp2[i].X == 1)
			dp2[i].Y = 1;
		upd(all - a[i] + 1, dp2[i]);
	}	
	for(int i = n;i >= 1;i--){
		if(dp1[i].X + dp2[i].X - 1 > mx){
			mx = dp1[i].X + dp2[i].X - 1, ans = dp1[i].Y * dp2[i].Y % mod;
		}
		else if(dp1[i].X + dp2[i].X - 1 == mx){
			ans = (ans + (dp1[i].Y * dp2[i].Y % mod)) % mod;
		}
	}
	for(int i = 1;i <= n - mx;i++)
		ans = ans * 2 % mod;
	printf("%d %lld", mx, ans);
}

Compilation message

zoltan.cpp: In function 'void squiz()':
zoltan.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
zoltan.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%d", a + i), tmp.push_back(MP(a[i], i));
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3436 KB Output is correct
4 Correct 2 ms 3436 KB Output is correct
5 Correct 2 ms 3436 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 3 ms 3564 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct
9 Correct 3 ms 3564 KB Output is correct
10 Correct 3 ms 3564 KB Output is correct
11 Correct 66 ms 10368 KB Output is correct
12 Correct 58 ms 9508 KB Output is correct
13 Correct 53 ms 9196 KB Output is correct
14 Correct 80 ms 9756 KB Output is correct
15 Correct 107 ms 11320 KB Output is correct
16 Correct 121 ms 12620 KB Output is correct
17 Correct 82 ms 11960 KB Output is correct
18 Correct 83 ms 11852 KB Output is correct
19 Correct 82 ms 11832 KB Output is correct
20 Correct 82 ms 11832 KB Output is correct