Submission #696658

#	Time	Username	Problem	Language	Result	Execution time	Memory
696658		uylulu	Izbori (COCI22_izbori)	C++17	110 / 110	586 ms	44828 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

const int N = 4e5;

int num[N + 1],n;

map<int,vector<int>> mp;

struct node{
    int len = 0,val = 0,sum = 0;
};

int lz[4*N + 1];
node seg[4*N + 1];

void build(int id,int l,int r) {
    seg[id].len = (r - l + 1);

    if(l == r) {
        return;
    }
    int mid = (l + r)/2;
    build(id*2,l,mid);
    build(id*2 + 1,mid + 1,r);

}

node merge(node i1,node i2) {

    node res;
    res.len = i1.len + i2.len;

    res.val = (i1.val + i1.sum * i2.len + i2.val);
    res.sum = (i1.sum + i2.sum);

    return res;
}

void add(int id,int l,int r,int x) {
    lz[id] += x;

    int sz = seg[id].len,asd = (sz + 1) * sz / 2;

    seg[id].sum += (x * sz);
    seg[id].val += (x * asd);
}

void down(int id,int l,int r) {
    int t = lz[id];
    if(lz[id] == 0) return;
    lz[id] = 0;

    int mid = (l + r)/2;

    add(id*2,l,mid,t);
    add(id*2 + 1,mid + 1,r,t);
}

void update(int id,int l,int r,int u,int v,int x) {
    if(v < l || u > r) return;
    if(u <= l && v >= r) {
        add(id,l,r,x);

        return;
    }
    down(id,l,r);
    int mid = (l + r)/2;

    update(id*2,l,mid,u,v,x);
    update(id*2 + 1,mid + 1,r,u,v,x);

    seg[id] = merge(seg[id*2],seg[id*2 + 1]);
}

node query(int id,int l,int r,int u,int v) {
    if(v < l || u > r) return {0,0,0};
    if(u <= l && v >= r) {
        // cout<<l<<" "<<r<<endl;
        // cout<<seg[id].len<<" "<<seg[id].val<<" "<<seg[id].sum<<endl;

        return seg[id];
    }

    down(id,l,r);
    int mid = (l + r)/2;
    return merge(query(id*2,l,mid,u,v),query(id*2 + 1,mid + 1,r,u,v));
}
struct change{
    int l,r,x;
};

vector<change> thay;

inline void upd(int l,int r,int x) {
    thay.push_back({l,r,-x});

    update(1,0,2*n,l,r,x);
}

int res = 0;

inline void cal(vector<int> st) {

    int lst = 0;

    upd(n - (st[0] - 1),n,1);

    for(int i = 0;i < st.size();i++) {
        int nxt;
        lst++;


        if(i < st.size() - 1) {
            nxt = st[i + 1] - 1;
        } else {
            nxt = n;
        }

        node tmp = query(1,0,2*n,2*lst + n - nxt - 1,2*lst + n - st[i] - 1);

        res += tmp.val;
        tmp = query(1,0,2*n,0,2*lst + n - nxt - 2);

        res += tmp.sum * (nxt - st[i] + 1);

        upd(n - nxt + 2*lst,n - st[i] + 2*lst,1);
    }
    for(auto u : thay) {
        update(1,0,2*n,u.l,u.r,u.x);
    }

    thay.clear();
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);

    cin>>n;
    for(int i = 1;i <= n;i++) {
        cin>>num[i];
        mp[num[i]].push_back(i);
    }
    build(1,0,2*n);

    for(auto u : mp) {
        cal(u.second);  
    }
    cout<<res<<endl;
}           

Compilation message (stderr)

Main.cpp: In function 'void cal(std::vector<long long int>)':
Main.cpp:112:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 0;i < st.size();i++) {
      |                   ~~^~~~~~~~~~~
Main.cpp:117:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         if(i < st.size() - 1) {
      |            ~~^~~~~~~~~~~~~~~

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