oj.uz

답안 #943457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943457 2024-03-11T13:34:21 Z idiotcomputer Zoltan (COCI16_zoltan) C++11
56 / 140
 224 ms 18584 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first 
#define s second
#define ll long long int

const int mxN = 2*1e5;
int n;

pii decr[mxN];

pii segtree[4*mxN+1];
pii segtree2[4*mxN+1];

pii comb(pii a, pii b){
    if (a.f == b.f){
        return {a.f,a.s+b.s};
    } 
    if (a.f > b.f){
        return a;
    }
    return b;
}

void upd(int t, pii v, bool w, int l = 0, int r = n-1, int idx = 0){
    if (l > t || r < t){
        return;
    }
    if (l == r){
        if (w) segtree[idx] = v;
        else segtree2[idx] = v;
        return;
    }
    int m = (l+r)/2;
    upd(t,v,w,l,m,2*idx+1);
    upd(t,v,w,m+1,r,2*idx+2);
    if (w) segtree[idx] = comb(segtree[2*idx+1],segtree[2*idx+2]);
    else segtree2[idx] = comb(segtree2[2*idx+1],segtree2[2*idx+2]);
    return;
}

pii query(int tl, int tr, bool w, int l = 0, int r = n-1, int idx = 0){
    if (l > r){
        return {0,0};
    }
    if (l > tr || r < tl){
        return {0,0};
    }
    if (l >= tl && r <= tr){
        if (w) return segtree[idx];
        return segtree2[idx];
    }
    int m = (l+r)/2;
    return comb(query(tl,tr,w,l,m,2*idx+1),query(tl,tr,w,m+1,r,2*idx+2));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    
    vector<int> vals(n);
    vector<pii> temp(n);
    for (int i = 0; i < n; i++){
        cin >> vals[i];
        temp[i].f = vals[i];
        temp[i].s =  i;
    }
    sort(temp.begin(),temp.end());
    int curr = -1;
    int cnt = -1;
    for (int i =0; i < n; i++){
        if (temp[i].f != curr){
            curr = temp[i].f;
            cnt++;
        }
        vals[temp[i].s] = cnt;
    }
    
    for (int i =0; i < n; i++) decr[i] = {0,0};
    for (int i =0; i < 4*mxN+1; i++) segtree[i] = {0,0};
    for (int i = n - 1; i >= 0; i--){
        decr[i] = query(0,vals[i]-1,1);
        decr[i].f += 1;
        if (decr[i].f == 1){
            decr[i].s += 1;
        }
        upd(vals[i],decr[i],1);
    }
    
    for (int i =0; i < 4*mxN+1; i++) segtree2[i] = {0,0};
  /*  for (int i =0; i < n; i++) cout << decr[i].f << ',' << decr[i].s << " ";
    cout << '\n';
    for (int i =0; i < n; i++) cout << vals[i] << " ";
    cout << '\n';*/
    curr = -1;
    cnt = 0;
    pii c,c2;
    for (int i =0; i < n; i++){
        c = query(0,vals[i]-1,0);
        c.f += 1;
        c2 = query(0,vals[i]-1,1);
        c2.f += 1;
        if (c2.f == 1) c2.s += 1;  
        c = max(c,c2);
        /*if (c2.f == c.f){
            c.s += c2.s;
        }*/
        if (c.f > curr){
            curr = c.f;
            cnt = c.s;
        } else if (c.f == curr){
            cnt += c.s;
        }
        //cout << c.f << "," << c.s << " ";
        upd(vals[i],c,0);
    }
    //cout << '\n';
    ll mod = 1e9+7;
    ll res = cnt;
    for (int i = 0; i < n-curr; i++){
        res = (res*2) % mod;
    }
    cout << curr << " " << res << "\n";

    
    
    
    return 0;
}

Subtask #1
56.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Incorrect 3 ms 12892 KB Output isn't correct
8 Correct 3 ms 12892 KB Output is correct
9 Incorrect 3 ms 12892 KB Output isn't correct
10 Correct 4 ms 12892 KB Output is correct
11 Incorrect 143 ms 17116 KB Output isn't correct
12 Incorrect 124 ms 16468 KB Output isn't correct
13 Incorrect 117 ms 16500 KB Output isn't correct
14 Incorrect 180 ms 16988 KB Output isn't correct
15 Incorrect 191 ms 17748 KB Output isn't correct
16 Incorrect 224 ms 18584 KB Output isn't correct
17 Incorrect 184 ms 18516 KB Output isn't correct
18 Incorrect 184 ms 17968 KB Output isn't correct
19 Incorrect 188 ms 18000 KB Output isn't correct
20 Incorrect 189 ms 18036 KB Output isn't correct