Submission #877744

#	Time	Username	Problem	Language	Result	Execution time	Memory
877744		HossamHero7	Izbori (COCI22_izbori)	C++14	110 / 110	485 ms	110648 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct segTree{
    vector<ll> tree , tree2;
    vector<pair<ll,bool>> lazy;
    int n;
    segTree(int _n){
        n = _n;
        tree.resize(4*(2*n+1)+5) , tree2.resize(4*(2*n+1)*5) , lazy.resize(4*(2*n+1)+5);
    }
    void prop(int node,int l,int r){
        if(lazy[node].second){
            tree[node] = 0;
            tree2[node] = 0;
            if(l != r){
                lazy[node << 1] = {0,1};
                lazy[node << 1 | 1] = {0,1};
            }
            lazy[node].second = 0;
        }
        tree[node] += lazy[node].first * (r - l + 1);
        ll sz = r - l + 1;
        ll x = sz * (sz + 1) / 2;
        tree2[node] += (x + sz * (2*n+1 - r)) * lazy[node].first;
        if(l != r){
            lazy[node << 1].first += lazy[node].first;
            lazy[node << 1 | 1].first += lazy[node].first;
        }
        lazy[node].first = 0;
    }
    void update(int node,int l,int r,int lQ,int rQ){
        if(l > r) return;
        if(lazy[node].first || lazy[node].second) prop(node,l,r);
        if(l > rQ || lQ > r) return;
        if(lQ <= l && r <= rQ) return lazy[node].first ++, prop(node,l,r) , void();
        int md = l + r >> 1;
        update(node<<1,l,md,lQ,rQ) , update(node<<1|1,md+1,r,lQ,rQ);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
        tree2[node] = tree2[node << 1] + tree2[node << 1 | 1];
    }
    ll query1(int node,int l,int r,int lQ,int rQ){
        if(l > r) return 0;
        if(lazy[node].first || lazy[node].second) prop(node,l,r);
        if(l > rQ || lQ > r) return 0;
        if(lQ <= l && r <= rQ) return tree[node];
        int md = l + r >> 1;
        return query1(node<<1,l,md,lQ,rQ) + query1(node<<1|1,md+1,r,lQ,rQ);
    }
    ll query2(int node,int l,int r,int lQ,int rQ){
        if(l > r) return 0;
        if(lazy[node].first || lazy[node].second) prop(node,l,r);
        if(l > rQ || lQ > r) return 0;
        if(lQ <= l && r <= rQ) return tree2[node];
        int md = l + r >> 1;
        return query2(node<<1,l,md,lQ,rQ) + query2(node<<1|1,md+1,r,lQ,rQ);
    }
    void clear(){
        lazy[1] = {0,1};
        prop(1,1,2*n+1);
    }
    void update(int l,int r){
        if(l > r) swap(l,r);
        update(1,1,2*n+1,l+n+1,r+n+1);
    }
    ll query1(int l,int r){
        if(l > r) swap(l,r);
        return query1(1,1,2*n+1,l+n+1,r+n+1);
    }
    ll query2(int l,int r){
        if(l > r) swap(l,r);
        return query2(1,1,2*n+1,l+n+1,r+n+1);
    }
};
void compress(vector<int> &a){
    int n = a.size();
    vector<pair<int,int>> b(n);
    for(int i=0;i<n;i++){
        b[i].first = a[i];
        b[i].second = i;
    }
    sort(b.begin(),b.end());
    a[b[0].second] = 1;
    int cnt = 1;
    for(int i=1;i<n;i++){
        if(b[i].first == b[i-1].first){
            a[b[i].second] = a[b[i-1].second];
        }
        else a[b[i].second] = ++cnt;
    }
}
void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(auto &i:a) cin>>i;
    compress(a);
    vector<vector<int>> idx(n+1);
    for(int i=0;i<n;i++) idx[a[i]].push_back(i);
    segTree sg(n);
    ll ans = 0;
    for(auto v : idx){
        if(v.empty()) continue;
        int p = 0;
        v.push_back(n);
        sg.update(p,p-v[0]);
        for(int i=0;i<v.size()-1;i++){
            p = 2 * i - v[i] + 1;
            int cnt = v[i+1] - v[i];
            ans += sg.query1(-n,p-cnt) * cnt;
            if(cnt > 1) ans += sg.query2(p-cnt+1,p-1) - sg.query1(p-cnt+1,p-1) * (n-(p-1));
            sg.update(p,p-cnt+1);
        }
        sg.clear();
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void segTree::update(int, int, int, int, int)':
Main.cpp:38:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'll segTree::query1(int, int, int, int, int)':
Main.cpp:48:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'll segTree::query2(int, int, int, int, int)':
Main.cpp:56:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int i=0;i<v.size()-1;i++){
      |                     ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 70 / 70