oj.uz

답안 #672079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
672079 2022-12-14T17:00:41 Z neki Izbori (COCI22_izbori) C++14
25 / 110
 119 ms 2900 KB 
#include <bits/stdc++.h>
#define ll int
#define vc vector

using namespace std;
struct segtr{
    struct node{
        node* lc=0,* rc=0;
        ll sum=0,sum2=0, upd=0, l, r, mid;
        node(ll l_, ll r_):l(l_), r(r_){mid=l+r;if(mid<0)--mid;mid/=2;}
        inline ll getlen(){return r-l+1;}
        inline ll getsum(){return sum+upd*getlen();}
        inline ll getsum2(){return sum2+upd*getlen()*(getlen()+1)/2;}
        void push(){
            if(!lc) lc=new node(l, mid);
            if(!rc) rc=new node(mid+1, r);
            if(upd){lc->upd+=upd, rc->upd+=upd;upd=0;}
        }
        void updsums(){
            sum=lc->getsum()+rc->getsum();
            sum2=lc->getsum2()+lc->getsum()*rc->getlen()+rc->getsum2();
        }
    };
    
    node* root;
    ll n;

    void update_w(ll ql, ll qr, node* no){
        assert(ql<=qr && -n<=ql && qr<=n);
        if(ql==no->l && qr==no->r) ++no->upd;
        else{
            no->push();
            if(qr<=no->mid) update_w(ql, qr, no->lc);
            else if(no->mid<ql) update_w(ql, qr, no->rc);
            else update_w(ql, no->mid, no->lc), update_w(no->mid+1, qr, no->rc);
            no->updsums();
        }
    }
    void update(ll ql, ll qr){update_w(ql, qr, root);}
    
    pair<ll, ll> query(ll ql, ll qr, node* no){
        assert(ql<=qr && -n<=ql && qr<=n);
        if(ql==no->l && qr==no->r) return make_pair(no->getsum(), no->getsum2());
        else{
            pair<ll, ll> ret;
            no->push();
            if(qr<=no->mid) ret=query(ql, qr, no->lc);
            else if(no->mid<ql) ret=query(ql, qr, no->rc);
            else{
                auto r1=query(ql, no->mid, no->lc);
                auto r2=query(no->mid+1, qr, no->rc);
                ret=make_pair(r1.first+r2.first, r1.second+r1.first*(qr-no->mid)+r2.second);
            } 
            no->updsums();
            return ret;
        }
    }
    ll get(ll ql, ll qr){
        assert(ql<=qr);
        assert(-n<=ql);
        assert(qr<=n);
        return query(-n, ql-1, root).first*(qr-ql+1)+query(ql, qr, root).second;
    }
    segtr(ll n_): n(n_){root=new node(-n, n);}
};

int main() {
    segtr sg(10);
    sg.update(2, 6);
    //cout << sg.query(3, 6, sg.root).second<<endl;
    //cout << sg.query(-1, 7, sg.root).first<<endl;
    
    ll n; cin >> n;
    vc<ll> a(n+1);for(ll i=1;i<=n;++i) cin >> a[i];
    map<ll, vc<ll>> poss; for(ll i=1;i<=n;++i) poss[a[i]].push_back(i);
    ll ans=0;
    for(auto [key, pos]: poss){
        segtr sg(n+4);
        pos.insert(pos.begin(), 0);
        ll cur=0;sg.update(0, 0);
        for(ll i=0;i+1<pos.size();++i){
            ll d=pos[i+1]-pos[i]-1; assert(d>=0);
            if(d>0)ans+=sg.get(cur-d-1, cur-2), sg.update(cur-d, cur-1);
            cur-=d;
            
            ++cur;
            ans+=sg.get(cur-1, cur-1);
            sg.update(cur, cur);
        }
        ll d=n+1-pos.back()-1;
        if(d>0)ans+=sg.get(cur-d-1, cur-2);
        cur-=d;
    }
    cout << ans << endl;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [key, pos]: poss){
      |              ^
Main.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(ll i=0;i+1<pos.size();++i){
      |                    ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 4 ms 1108 KB Output is correct
12 Correct 4 ms 1108 KB Output is correct
13 Correct 4 ms 1176 KB Output is correct
14 Correct 4 ms 1092 KB Output is correct
15 Correct 4 ms 1108 KB Output is correct
16 Correct 4 ms 1076 KB Output is correct
17 Correct 2 ms 468 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 119 ms 2112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 4 ms 1108 KB Output is correct
12 Correct 4 ms 1108 KB Output is correct
13 Correct 4 ms 1176 KB Output is correct
14 Correct 4 ms 1092 KB Output is correct
15 Correct 4 ms 1108 KB Output is correct
16 Correct 4 ms 1076 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Incorrect 119 ms 2112 KB Output isn't correct
19 Halted 0 ms 0 KB -