답안 #642510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642510	2022-09-19T17:26:51 Z	red24	Izbori (COCI22_izbori)	C++14	컴파일 오류	0 ms	0 KB

Main

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

#define vi vector<int> 
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ppi pair<pair<int, int>>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define OK cout << "OK" << '\n'
#define qi queue<int>
#define sti stack<int>
#define si stack<int>
#define yes cout << "Yes" << '\n'
#define no cout << "No" << '\n'
#define pb push_back
#define eb emplace_back
#define vpi vector<pair<int, int>>
#define ll long long
#define nl cout << '\n'
#define ok cout << "OK" << '\n'
#define mp make_pair
#define repr(i, b, a) for (int i = b; i >= a; i--)
#define veb vector<bool>
#define vveb vector<vector<bool>>
#define int long long

void printvec(vi v)
{
	rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
}

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

long long binpowmod(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

void compress(vi &a)
{
	int n = a.size() - 1;
	vpi pairs(n+1);
	rep(i, 1, n) pairs[i] = mp(a[i],i);
	sort(pairs.begin(), pairs.end());

	int c = 1;
	rep(i, 1, n)
	{
		if (pairs[i].first > pairs[i-1].first && i > 1) c++;
		a[pairs[i].second] = c;
	}
	return;
}

// PROGRAM
const int MOD = (int)1e9 + 7;

void build(int v, int l, int r, vi &a, vi &seg, vi &seg_val)
{
	// cout << v << "  " << l << ' ' << r << endl;
	if (l == r)
	{
		return;
	}

	int mid = (l + r)/2;

	build(v<<1, l, mid, a, seg, seg_val);
	build((v<<1) + 1, mid + 1, r, a, seg, seg_val);

	vi vec;
	rep(i, l - 1, mid - 1) vec.pb(a[i]);
	sort(vec.begin(), vec.end());

	int curr_res = 0;
	rep(i, mid + 1, r)
	{
		auto it = lower_bound(vec.begin(), vec.end(), a[i]);
		curr_res += max(0, it - vec.begin());
	}
	seg_val[v]  = curr_res + seg_val[v<<1] + seg_val[(v<<1)+1];
}

void solve()
{
	// CHECK IF PROGRAM HAS TESTCASES
	int n; cin >> n;
	vi a(n+1);
	rep(i, 1, n) cin >> a[i];
	compress(a);

	int mx = -1;
	rep(i, 1, n) mx = max(mx, a[i]);

	int res = 0;

	rep(c, 1, mx)
	{
		vi b(n+1);
		rep(i, 1, n) 
		{
			if (a[i] == c) b[i] = 1;
			else b[i] = 0;
		}
		vi pf(n+1);
		rep(i, 1, n) pf[i] = pf[i-1] + b[i];
		rep(i, 1, n) b[i] = 2*pf[i] - i;

		vi seg_val(4*n+10);
		vi seg(4*n+10);

		build(1, 1, n, b, seg, seg_val);

		res += seg_val[1] + pf[n];
	}

	cout << res << '\n';
}

int32_t main()
{
	//fastio
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//fastio
	
	int T = 1;
	//cin >> T;
	while (T--) solve();
}

Compilation message

Main.cpp: In function 'void printvec(std::vector<long long int>)':
Main.cpp:8:40: 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]
    8 | #define rep(i, a, b) for (int i = a; i <= b; i++)
......
   29 |  rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
      |      ~~~~~~~~~~~~~~~~                   
Main.cpp:29:2: note: in expansion of macro 'rep'
   29 |  rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
      |  ^~~
Main.cpp: In function 'void build(long long int, long long int, long long int, std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&)':
Main.cpp:95:38: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type)'
   95 |   curr_res += max(0, it - vec.begin());
      |                                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:95:38: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'})
   95 |   curr_res += max(0, it - vec.begin());
      |                                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:95:38: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'})
   95 |   curr_res += max(0, it - vec.begin());
      |                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:95:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   95 |   curr_res += max(0, it - vec.begin());
      |                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:95:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   95 |   curr_res += max(0, it - vec.begin());
      |                                      ^