Submission #997231

#TimeUsernameProblemLanguageResultExecution timeMemory
997231TsotneSVZoltan (COCI16_zoltan)C++17
42 / 140
176 ms27064 KiB
#pragma gcc diagnostic "-std=c++1z" #include <bits/stdc++.h> using namespace std; /* /\_/\ (= ._.) / > \> */ //#pragma comment(linker, "/stack:200000000") // #define int long long #define fi first #define se second #define pb push_back #define ins insert #define mp make_pair #define send {ios_base::sync_with_stdio(false);} #define help {cin.tie(0);} #define endl '\n' #define sz(x) ((long long) (x).size()) #define all(x) (x).begin(),(x).end() #define print(x) cout<<(x)<<" "; #define printl(x) cout<<(x)<<endl #define dbg(x) cerr<<#x<<" "<<x<<endl typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pii> vpi; typedef vector<pll> vpl; void fileIO(string filename) { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } const ll MOD = 1e9+7; // const ll mod = 998244353; // ll mod; const int inf=1e9,MAXN=2e5+1; const ll INF=1e18; const ld pi = 3.14159265358979323846; // typedef long long ll; template<typename Node,typename Update> struct Segtr { int s; vector<Node> tree; void build(int v,int tl,int tr) { if(tl == tr) { tree[v] = Node(); }else { int tm = (tl + tr)/2; build(2*v,tl,tm); build(2*v+1,tm+1,tr); tree[v].merge(tree[2*v],tree[2*v+1]); } } void update(int v,int idx,int tl,int tr,Update addend) { if(tl == tr) { addend.apply(tree[v]); }else { int tm = (tl + tr)/2; if(idx <= tm) update(2*v,idx,tl,tm,addend); else update(2*v+1,idx,tm+1,tr,addend); tree[v].merge(tree[2*v],tree[2*v+1]); } } Node query(int v,int l,int r,int tl,int tr) { if(l > r) return Node(); // * else if(tl == l && tr == r) return tree[v]; int tm = (tl + tr)/2; Node L,R,ans; L = query(2*v,l,min(r,tm),tl,tm); R = query(2*v+1,max(l,tm+1),r,tm+1,tr); ans.merge(L,R); return ans; } Segtr(int n) { s = n; tree.resize(4*n); build(1,0,n-1); } }; struct Node1 { ll mx,cnt; // * shecvla sheidzleba void merge(Node1 &a,Node1 &b) { if(a.mx > b.mx) { mx = a.mx; cnt = a.cnt; }else if(a.mx < b.mx) { mx = b.mx; cnt = b.cnt; }else { mx = a.mx; cnt = (a.cnt % MOD + b.cnt % MOD) % MOD; } } Node1() : mx(0),cnt(0) {} }; struct Update1 { int val; ll cnt; Update1(int val,ll cnt) { this->val = val; this->cnt = cnt; } void apply(Node1 &a) { if(val > a.mx) { a.mx = val; a.cnt = cnt; }else if(val == a.mx) { a.cnt = (a.cnt % MOD + cnt % MOD) % MOD; } } }; int n; ll binpow(int a,ll b) { ll res = 1; while(b) { if(b&1) res = res * a % MOD; a = a * a % MOD; b/=2; } return res; } void solve(int tc = 0){ cin>>n; vi A,v; for(int i=0;i<n;i++) { int tmp; cin>>tmp; A.pb(tmp); v.pb(tmp); } sort(all(v)); v.resize(unique(all(v)) - v.begin()); for(int i=0;i<n;i++) { A[i] = lower_bound(all(v),A[i]) - v.begin() + 1; } Segtr<Node1,Update1> T1(sz(v) + 1),T2(sz(v) + 1); int len = 0; ll cnt = 0; for(int i=sz(A)-1;i>=0;i--) { Node1 x1 = T1.query(1,0,A[i]-1,0,sz(v)); Node1 x2 = T2.query(1,A[i]+1,sz(v),0,sz(v)); x1.cnt = max(x1.cnt,1ll); x2.cnt = max(x2.cnt,1ll); int tLen = x1.mx + x2.mx + 1; ll tCnt = x1.cnt * x2.cnt % MOD; if(tLen > len) { len = tLen; cnt = tCnt; }else if(tLen == len) { cnt = (cnt + tCnt) % MOD; } // ...... T1.update(1,A[i],0,sz(v),Update1(x1.mx + 1,x1.cnt)); T2.update(1,A[i],0,sz(v),Update1(x2.mx + 1,x2.cnt)); } cout<<len<<" "<<cnt * binpow(2,n - len) % MOD<<endl; } signed main(){ send help int tc=1; // cin>>tc; for(int t = 0; t < tc; t++) solve(t); }

Compilation message (stderr)

zoltan.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
zoltan.cpp: In function 'void fileIO(std::string)':
zoltan.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...