답안 #943506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943506 2024-03-11T14:33:41 Z idiotcomputer Zoltan (COCI16_zoltan) C++11
35 / 140
227 ms 16916 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] = comb(v,segtree[idx]);
        else segtree2[idx] = comb(v,segtree2[idx]);
        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 (tl > tr){
       // cout << "HEr\n";
        return {0,1};
    }
    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};
    upd(0,{0,1},1);
    for (int i = n - 1; i > 0; i--){
      //  cout << vals[i]-1 << " ";
        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};
    upd(0,{0,1},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;  
        if (c.f < c2.f){
            swap(c,c2);
        }
        if (c2.f == c.f && c.f != 1){
            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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 12892 KB Output isn't correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 4 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 4 ms 12892 KB Output isn't correct
8 Incorrect 4 ms 12892 KB Output isn't correct
9 Incorrect 3 ms 12892 KB Output isn't correct
10 Incorrect 3 ms 12892 KB Output isn't correct
11 Incorrect 149 ms 16068 KB Output isn't correct
12 Incorrect 136 ms 15444 KB Output isn't correct
13 Incorrect 126 ms 15440 KB Output isn't correct
14 Incorrect 164 ms 15680 KB Output isn't correct
15 Incorrect 192 ms 16328 KB Output isn't correct
16 Incorrect 227 ms 16916 KB Output isn't correct
17 Incorrect 196 ms 16704 KB Output isn't correct
18 Incorrect 198 ms 16724 KB Output isn't correct
19 Incorrect 184 ms 16716 KB Output isn't correct
20 Incorrect 215 ms 16892 KB Output isn't correct