Submission #370960

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
370960	2021-02-25T09:12:57 Z	maozkurt	Zoltan (COCI16_zoltan)	C++17	112 / 140	558 ms	23744 KB

zoltan

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn = 2e5+5;
const int mod = 1e9+7;

ll binpow(ll n, ll r){
    ll ret = 1;
    while(r){
        if(r&1)
            ret = ret * n % mod;
        n = n * n % mod;
        r >>= 1;
    }
    return ret;
}   

struct node{
    int len;
    int tane;
};

struct segtree{
    vector<node> t;
    int n;
    segtree (int size){
        n = size;
        t = vector<node>(4 * size);
    }
    node query(int l, int r){
        if(l>r)
            return {0,0};
        return _q(l,r,1,n,1);
    }
    void setit(ll pos, ll tane, ll len){
        _i(pos,tane,len,1,n,1);
    }
    private:
    node _q(int l, int r, int tl, int tr, int v){
        if(tl>tr || tl>r || tr<l)
            return {0,0};
        if(tl>=l && tr <= r)
            return t[v];
        int tm = (tl+tr)/2;
        node sol = _q(l,r,tl,tm,2*v);
        node sag = _q(l,r,tm+1,tr,2*v+1);
        if(sol.len == sag.len){
            return {sol.len,(sol.tane + sag.tane) % mod};
        }
        else if(sol.len>sag.len)
            return sol;
        else
            return sag;
    }
    void _i(ll pos, ll tane, ll len, int tl, int tr, int v){
        if(tl > tr || tl > pos || tr < pos)
            return;
        if(tl == tr){
            assert(tl == pos);
            //assert(t[v].len == 0 && t[v].tane == 0);
            if(t[v].len < len){
                t[v].len = len;
                t[v].tane = tane;
            }
            else if(t[v].len == len){
                t[v].tane = (t[v].tane + tane) % mod;//+=
            }
            return;
        }

        int tm = (tl+tr)/2;
        _i(pos,tane,len,tl,tm,2*v);
        _i(pos,tane,len,tm+1,tr,2*v+1);

        if(t[2*v].len > t[2*v+1].len){
            t[v] = t[2*v];
        }
        else if(t[2*v].len < t[2*v+1].len){
            t[v] = t[2*v+1];
        }
        else{
            t[v] = {t[2*v].len, (t[2*v].tane + t[2*v+1].tane) % mod};
        }
        return;
    }
};

int main(){

    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);

    int n;cin>>n;

    vector<int> arr(n);
    vector<int> sorted;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        sorted.pb(arr[i]);
    }
    sort(sorted.begin(),sorted.end());
    sorted.resize(unique(sorted.begin(),sorted.end()) - sorted.begin());
    map<int,int> mm;
    for(int i=1;i<=(int)sorted.size();i++){
        mm[sorted[i-1]] = i;
    }

    for(int i=0;i<(int)arr.size();i++){
        arr[i] = mm[arr[i]];
    }
    
    segtree inctree(n+1), dectree(n+1);
    
    ll ans = 0;
    ll anslen = 0;

    for(int i=n-1;i>=0;i--){
        node sol = dectree.query(arr[i]+1,n);
        node sag = inctree.query(1,arr[i]-1);
        ll curlen = sol.len + sag.len + 1;
        
        ll curtane;
        if(sol.tane == 0 && sag.tane == 0)
            curtane = 1;
        else if(sol.tane == 0)
            curtane = sag.tane;
        else if(sag.tane == 0)
            curtane = sol.tane;
        else
            curtane = sol.tane * sag.tane % mod;
        
        curtane = curtane * binpow(2,n-curlen) % mod;      

        if(curlen>anslen){
            ans = curtane;
            anslen = curlen;
        }
        else if(curlen == anslen){
            ans = (ans + curtane) % mod;
        }
        //cerr << arr[i] << sp << sol.len << sp << sol.tane << endl;
        //cerr << arr[i] << sp << sag.len << sp << sag.tane << endl;
        dectree.setit(arr[i],max(1,sol.tane),sol.len+1);
        inctree.setit(arr[i],max(1,sag.tane),sag.len+1);
    }

    cout << anslen << sp << ans << endl;

}       

Subtask #1

112.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Incorrect	2 ms	492 KB	Output isn't correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	304 ms	18920 KB	Output is correct
12	Correct	263 ms	16488 KB	Output is correct
13	Correct	256 ms	15452 KB	Output is correct
14	Incorrect	367 ms	16616 KB	Output isn't correct
15	Incorrect	456 ms	20456 KB	Output isn't correct
16	Incorrect	558 ms	23744 KB	Output isn't correct
17	Correct	404 ms	22376 KB	Output is correct
18	Correct	430 ms	22380 KB	Output is correct
19	Correct	407 ms	22376 KB	Output is correct
20	Correct	431 ms	22436 KB	Output is correct