Submission #635236

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
635236	2022-08-25T17:17:28 Z	IWTIM	Zoltan (COCI16_zoltan)	C++14	98 / 140	362 ms	17968 KB

zoltan

# include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int mod = 1e9 + 7;
const int N = 3e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
struct DSU {
	vi e; void init(int N) { e = vi(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
 
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
#define dec decc
#define int long long
int n,a[N],inc[N],dec[N],cntinc[N],cntdec[N];
pii tree[4 * N][2];
pii merge(pii a, pii b){
    pii c = {0,0};
    if (a.f != b.f) c = max(a,b);
    else c = {a.f, b.s + a.s};
    return c;
}
void update(int node, int le, int ri, int idx, int val, int raod, int ty) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        if (tree[node][ty].f > val) return ;
        if (tree[node][ty].f < val) {
            tree[node][ty] = {val, raod};
            return ;
        }
        tree[node][ty].s += raod;
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node,le,mid,idx,val,raod,ty);
    update(2 * node + 1, mid + 1, ri, idx,val,raod,ty);
    tree[node][ty] = merge(tree[2 * node][ty], tree[2 * node + 1][ty]);
}
pii getans(int node, int le, int ri, int start, int end,int ty) {
    if (le > end || ri < start) return {0,0};
    if (le >= start && ri <= end) {
        return tree[node][ty];
    }
    int mid = (le + ri) / 2;
    return merge(getans(2 * node,le,mid,start,end,ty), getans(2 * node + 1, mid + 1, ri, start,end,ty));
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    vector < pii > v;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        v.pb({a[i],i});
    }
    sort(v.begin(), v.end());
    a[v[0].s] = 1;
    for (int i = 1; i < v.size(); i++) {
        if (v[i].f != v[i - 1].f) a[v[i].s] = a[v[i - 1].s] + 1; 
        else a[v[i].s] = a[v[i - 1].s];
    }
    
    int mx = 0;
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        inc[i] = getans(1,1,n,a[i] + 1,n,0).f + 1;
        dec[i] = getans(1,1,n,1,a[i] - 1,1).f + 1;
        
        cntinc[i] = getans(1,1,n,a[i] + 1, n, 0).s;
        cntdec[i] = getans(1,1,n,1,a[i] - 1, 1).s;
        if (cntinc[i] == 0) cntinc[i] = 1; if (cntdec[i] == 0) cntdec[i] = 1;
        update(1,1,n, a[i], inc[i], cntinc[i],0);
        update(1,1,n, a[i], dec[i], cntdec[i],1);
        mx = max(mx, inc[i] + dec[i] - 1);
    }
    for (int i = n; i >= 1; i--) {
        if (inc[i] + dec[i] - 1 == mx) {
            ans += (cntinc[i] * cntdec[i]) % mod;
            ans %= mod;
        }
    }
    int x = 1;
    for (int i = 1; i <= n - mx; i++) x *= 2LL, x %= mod;
    cout<<mx<<" "<<ans * x % mod<<"\n";
}

Compilation message

zoltan.cpp:215:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  215 | main() {
      | ^~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:225:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp:238:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  238 |         if (cntinc[i] == 0) cntinc[i] = 1; if (cntdec[i] == 0) cntdec[i] = 1;
      |         ^~
zoltan.cpp:238:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  238 |         if (cntinc[i] == 0) cntinc[i] = 1; if (cntdec[i] == 0) cntdec[i] = 1;
      |                                            ^~

Subtask #1

98.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Incorrect	246 ms	16040 KB	Output isn't correct
12	Incorrect	210 ms	15100 KB	Output isn't correct
13	Incorrect	187 ms	10652 KB	Output isn't correct
14	Incorrect	247 ms	15168 KB	Output isn't correct
15	Incorrect	330 ms	16728 KB	Output isn't correct
16	Incorrect	362 ms	17968 KB	Output isn't correct
17	Correct	299 ms	16704 KB	Output is correct
18	Correct	356 ms	16680 KB	Output is correct
19	Correct	303 ms	16900 KB	Output is correct
20	Correct	308 ms	16660 KB	Output is correct