제출 #1286050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286050		cowkim	Zoltan (COCI16_zoltan)	C++20	0 / 140	59 ms	1980 KiB

zoltan

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iomanip>
#define ll long long
#define int ll
#define endl "\n"
using namespace std;
ll MODNR = 1000000007;
pair<int,int> getMax(pair<int,int> a, pair<int,int> b){
    if((a.first == b.first) && a.first != 0) return {a.first,(a.second + b.second)%MODNR};
    return a.first < b.first ? b: a;
}
struct segNode{
    int nodel;
    int noder;
    pair<int,int> nodeMax;
    segNode* lNode = nullptr;
    segNode* rNode = nullptr;
    segNode(int nodel, int noder){
        this->nodel = nodel;
        this->noder = noder;
        nodeMax = {0,1};
    }
    void extend(){
        if(lNode == nullptr){
            int mid = (nodel + noder)/2;
            lNode = new segNode(nodel,mid);
            rNode = new segNode(mid,noder);
        }
    }
    pair<int,int> update(int pos, pair<int,int> change){
        if(pos < nodel || noder <= pos) return nodeMax;
        if(nodel +1 == noder) return nodeMax = getMax(nodeMax,change);
        extend();
        return nodeMax = getMax(lNode->update(pos,change), rNode->update(pos,change));
    }
    pair<int,int> querie(int l, int r){
        if(r <= nodel || noder <= l) return {0,1};
        if(l<= nodel && noder <= r) return nodeMax;
        return getMax(lNode->querie(l,r),rNode->querie(l,r));
    }
};
signed main(){
    //lathet
    segNode daSeg(0,MODNR);
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i<n; i++){
        cin >> arr[i];
    }
    //bygg upp om de läggs på vänstra sidan
    for(int i = n-1; i>= 0; i--){
        pair<int,int> best = daSeg.querie(0,arr[i]);
        best.first++;
        daSeg.update(arr[i],best);
    }
    //kan inte välja första elementet men måste pga ett trick
    for(int i = 0; i<n; i++){
        pair<int,int> best = daSeg.querie(0,arr[i]);
        best.first++;
        daSeg.update(arr[i],best);
    }
    pair<int,int> best = daSeg.querie(0,MODNR);
    // if(best.first == 1){
    //     int nrCombos = 1;
    //     for(int i = 1; i< n; i++){
    //         nrCombos <<= 1;
    //         nrCombos = nrCombos%MODNR;
    //     }
    //     nrCombos = (nrCombos*n)%MODNR;
    //     cout << 1 << " " << nrCombos << endl;
    //     return 0;
    // }
    //cout << best.first << " " << best.second << endl;
    int restCombos = 1;
    int nrNumsLeft = n - best.first;
    if(nrNumsLeft == 0) best.second>>=1;
    for(int i = 1; i<nrNumsLeft; i++){
        restCombos<<=1;
        restCombos%MODNR;
    }
    cout << best.first << " " << (restCombos*best.second)%MODNR << endl;
    return 0;
}

• Subtask 1: 0 / 140