Submission #838639

#	Time	Username	Problem	Language	Result	Execution time	Memory
838639		fanwen	Izbori (COCI22_izbori)	C++17	110 / 110	741 ms	59976 KiB

Main

#include <bits/stdc++.h>

using namespace std;


template <class T> struct Fenwick_Tree {
    vector<T> bit_add, bit_sub;
    int n;

    Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}

    void clear() { 
        fill(bit_add.begin(), bit_add.end(), T(0));
        fill(bit_sub.begin(), bit_sub.end(), T(0));
    }

    void update(int u, int v, T val) {
        for (int i = u; i <= n; i += i & -i) {
            bit_add[i] += val;
            bit_sub[i] += 1LL * (u - 1) * val;
        }
        for (int i = v; i <= n; i += i & -i) {
            bit_add[i] -= val;
            bit_sub[i] -= 1LL * v * val;
        }
    }
    
    void update(int u, T val) { update(u, u, val); }

    T get(int u) {
        T ans1 = 0, ans2 = 0;
        for (int i = u; i; i -= i & -i) {
            ans1 += bit_add[i];
            ans2 += bit_sub[i];
        }
        return u * ans1 - ans2;
    }

    T get(int l, int r) { return get(r) - get(l - 1); }
};

long long def(int x) { return 1LL * x * (x + 1) / 2; }

template <class T> 
struct lazy_segment_tree {
	#define mid ((l + r) >> 1)

    vector <T> it, lazy, start;
    int n;

    void push(int idx, int l, int r) {
    	if(lazy[idx] == 0 and start[idx] == 0) return;
    	it[idx] += lazy[idx] * def(r - l + 1) + start[idx] * (r - l + 1);
    	if(l != r) {
    		assert((2 * idx) <= 4 * n and (2 * idx + 1) <= 4 * n);
    		lazy[idx << 1] += lazy[idx];
    		lazy[idx << 1 | 1] += lazy[idx];
    		start[idx << 1] += start[idx];
    		start[idx << 1 | 1] += start[idx] + (mid - l + 1) * lazy[idx];
    	}
    	start[idx] = lazy[idx] = 0;
    }

    T merge(const T &a, const T &b) {
    	return a + b;
    }

    void update(int idx, int l, int r, int u, int v, T val) {
        push(idx, l, r);
        if(l > v || r < u) return;
        if(l >= u && r <= v) {
        	lazy[idx] += val;
        	start[idx] += val * (l - u);
	        push(idx, l, r);
	        return;
        }
        update(idx << 1, l, mid, u, v, val);
        update(idx << 1 | 1, mid + 1, r, u, v, val);
        it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
    }

    T get(int idx, int l, int r, int u, int v) {
        push(idx, l, r);
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return it[idx];
        return merge(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
    }
public :
    
    explicit lazy_segment_tree(int n) : 
        n(n), lazy(n << 2 | 1, 0), it(n << 2 | 1), start(n << 2 | 1) {}

    void update(int l, int r, T val) { 
        update(1, 1, n, l, r, val); 
    }

    T get(int l, int r) { 
        return get(1, 1, n, l, r); 
    }

    T get(int u) {
        return get(u, u);
    }
    #undef mid
};

const int MAXN = 2e5 + 5;

int n, a[MAXN];
vector <int> pos[MAXN];

void you_make_it(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
    	pos[i].push_back(0);
    	cin >> a[i];
    }
    vector <int> b(a + 1, a + n + 1);
    sort(b.begin(), b.end()); 
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int i = 1; i <= n; ++i) {
    	a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
    	pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
    	pos[i].emplace_back(n + 1);
    }
    Fenwick_Tree <long long> bit(2 * n + 1);
    lazy_segment_tree <long long> it(2 * n + 1);
    long long ans = 0;
    for (int u = 1; u <= n; ++u) {
    	for (int i = 0; i < pos[u].size() - 1; ++i) {
    		int r = 2 * (i + 1) - pos[u][i];
    		int l = r - (pos[u][i + 1] - pos[u][i] - 1);
    		ans += it.get(l - 1 + n, r - 1 + n) + bit.get(l - 1 + n, r - 1 + n);
    		it.update(l + n, r + n, 1);
    		bit.update(r + n + 1, 2 * n + 1, r - l + 1);
    	}

    	for (int i = 0; i < pos[u].size() - 1; ++i) {
			int r = 2 * (i + 1) - pos[u][i];
    		int l = r - (pos[u][i + 1] - pos[u][i] - 1);
    		it.update(l + n, r + n, - 1);
    		bit.update(r + n + 1, 2 * n + 1, -r + l - 1);	
    	}
    }
    cout << ans;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

Main.cpp: In function 'void you_make_it()':
Main.cpp:132:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |      for (int i = 0; i < pos[u].size() - 1; ++i) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:140:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |      for (int i = 0; i < pos[u].size() - 1; ++i) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(int) [with T = long long int]':
Main.cpp:128:43:   required from here
Main.cpp:8:9: warning: 'Fenwick_Tree<long long int>::n' will be initialized after [-Wreorder]
    8 |     int n;
      |         ^
Main.cpp:7:15: warning:   'std::vector<long long int, std::allocator<long long int> > Fenwick_Tree<long long int>::bit_add' [-Wreorder]
    7 |     vector<T> bit_add, bit_sub;
      |               ^~~~~~~
Main.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}
      |     ^~~~~~~~~~~~
Main.cpp: In instantiation of 'lazy_segment_tree<T>::lazy_segment_tree(int) [with T = long long int]':
Main.cpp:129:47:   required from here
Main.cpp:49:9: warning: 'lazy_segment_tree<long long int>::n' will be initialized after [-Wreorder]
   49 |     int n;
      |         ^
Main.cpp:48:20: warning:   'std::vector<long long int, std::allocator<long long int> > lazy_segment_tree<long long int>::lazy' [-Wreorder]
   48 |     vector <T> it, lazy, start;
      |                    ^~~~
Main.cpp:90:14: warning:   when initialized here [-Wreorder]
   90 |     explicit lazy_segment_tree(int n) :
      |              ^~~~~~~~~~~~~~~~~
Main.cpp:48:20: warning: 'lazy_segment_tree<long long int>::lazy' will be initialized after [-Wreorder]
   48 |     vector <T> it, lazy, start;
      |                    ^~~~
Main.cpp:48:16: warning:   'std::vector<long long int, std::allocator<long long int> > lazy_segment_tree<long long int>::it' [-Wreorder]
   48 |     vector <T> it, lazy, start;
      |                ^~
Main.cpp:90:14: warning:   when initialized here [-Wreorder]
   90 |     explicit lazy_segment_tree(int n) :
      |              ^~~~~~~~~~~~~~~~~

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