oj.uz

답안 #943792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943792 2024-03-11T23:05:13 Z idiotcomputer Zoltan (COCI16_zoltan) C++11
140 / 140
 247 ms 29476 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define f first 
#define s second
#define ll long long int
 
const int mxN = 2*1e5;
const ll mod = 1e9+7;
int n;
 
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) % mod};
    } 
    return max(a,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){
        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 < 4*mxN+1; i++) segtree[i] = {0,0};
    pii c,c2;
    for (int i = n - 1; i >= 0; i--){
        c = query(0,vals[i]-1,1);
        c = comb(c,{0,1});
        c.f += 1;
     //   cout << c.f << ',' << c.s << " ";
        upd(vals[i],c,1);
    }
  //  cout << '\n';
    for (int i =0; i < 4*mxN+1; i++) segtree2[i] = {0,0};
    for (int i = n-1; i >= 0; i--){
        c = query(vals[i]+1,n-1,0);
        c = comb(c,{0,1});
        c.f+=1;
      //  cout << c.f << "," << c.s << " ";
        upd(vals[i],c,0);
    }
  // cout << '\n';
 //   
    
    pii res = {1,n};
    for (int i = 0; i < n; i++){
        c = query(0,i-1,1);
        c = comb(c,{0,1});
        c2 = query(i,i,0);
   // //    c2 = comb(c2,{0,1});
    //    cout << i << ": " << c.f << ',' << c.s << " " << c2.f << ',' << c2.s << "\n";
     //   cout << c.f + c2.f << " ," << c.s*c2.s << "\n";
        res = comb(res,{c.f+c2.f,(c.s*c2.s)%mod});
    }
  //  cout << res.s << "\n";
    for (int i = 0; i < n-res.f; i++){
        res.s = (res.s*2) % mod;
    }
  //  cout << res.s << '\n';
    res.s = (res.s * 500000004) % mod;
    cout << res.f << " " << res.s << "\n";
    
    
    
    
    return 0;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25436 KB Output is correct
2 Correct 5 ms 25300 KB Output is correct
3 Correct 4 ms 25436 KB Output is correct
4 Correct 4 ms 25436 KB Output is correct
5 Correct 4 ms 25436 KB Output is correct
6 Correct 4 ms 25432 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 5 ms 25436 KB Output is correct
9 Correct 5 ms 25508 KB Output is correct
10 Correct 5 ms 25588 KB Output is correct
11 Correct 174 ms 28412 KB Output is correct
12 Correct 162 ms 28008 KB Output is correct
13 Correct 140 ms 27988 KB Output is correct
14 Correct 170 ms 28000 KB Output is correct
15 Correct 226 ms 28756 KB Output is correct
16 Correct 247 ms 29184 KB Output is correct
17 Correct 219 ms 29476 KB Output is correct
18 Correct 220 ms 29268 KB Output is correct
19 Correct 216 ms 29420 KB Output is correct
20 Correct 217 ms 29272 KB Output is correct