oj.uz

답안 #943562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943562 2024-03-11T15:21:29 Z idiotcomputer Zoltan (COCI16_zoltan) C++11
49 / 140
 264 ms 15440 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;
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};
    } 
    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,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.f += 1;
        c = max(c,{1,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.f += 1;
        c = max(c,{1,1});
       // cout << c.f << "," << c.s << " ";
        upd(vals[i],c,0);
    }
   // cout << '\n';
    
    
    curr = -1;
    ll res = 0;
    for (int i = 0; i < n; i++){
        c = query(0,vals[i]-1,1);
        c = max(c,{0,1});
        c2 = query(vals[i],vals[i],0);
        c2 = max(c2,{1,1});
      //  cout << c.f + c2.f << " ," << c.s*c2.s << " " << curr << '\n';
        if (c.f+c2.f> curr){
            curr = c.f+c2.f;
            res = (c.s*c2.s)%mod;
        } else if (c.f+c2.f == curr){
            res = (res + c.s*c2.s) % mod;
        }
    }
   // cout << res << '\n';
    for (int i = 0; i < n-curr; i++){
        res = (res*2) % mod;
    }
 //   cout << res << '\n';
    res = (res * 500000004) % mod;
    cout << curr << " " << res << "\n";
    
    
    
    
    return 0;
}

Subtask #1
49.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Incorrect 3 ms 12988 KB Output isn't correct
5 Correct 3 ms 12892 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Incorrect 4 ms 12892 KB Output isn't correct
10 Correct 3 ms 12888 KB Output is correct
11 Incorrect 173 ms 14664 KB Output isn't correct
12 Incorrect 168 ms 14580 KB Output isn't correct
13 Incorrect 139 ms 14324 KB Output isn't correct
14 Incorrect 183 ms 14428 KB Output isn't correct
15 Incorrect 218 ms 14800 KB Output isn't correct
16 Incorrect 257 ms 15140 KB Output isn't correct
17 Incorrect 220 ms 15328 KB Output isn't correct
18 Incorrect 264 ms 15140 KB Output isn't correct
19 Incorrect 231 ms 15440 KB Output isn't correct
20 Incorrect 219 ms 15188 KB Output isn't correct