Submission #361427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
361427	2021-01-30T04:28:23 Z	pure_mem	Zoltan (COCI16_zoltan)	C++14	140 / 140	121 ms	12620 KB

zoltan

#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

#	Verdict	Execution time	Memory	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