답안 #938790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938790	2024-03-05T14:27:27 Z	Lobo	자리 배치 (IOI18_seats)	C++17	컴파일 오류	0 ms	0 KB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e6+10;
const int B = 1000;

int n, m, col[maxn], row[maxn];
vector<pair<int,int>> mxB[maxn/B+10], mnB[maxn/B+10];
vector<int> vecmxmn[maxn/B+10];
unordered_map<int,vector<int>> vecmn[maxn/B+10], vecmx[maxn/B+10];

void construct(int b) {
	int l = b*B;
	int r = min(n*m-1,(b+1)*B-1);
	int mx = -inf;
	int mn = inf;
	// B * log
	for(int k = l; k <= r; k++) {
		if(col[k] > mx) {
			mx = col[k];
			mxB[b].pb(mp(col[k],k)); // crescente
		}
		if(col[k] < mn) {
			mn = col[k];
			mnB[b].pb(mp(col[k],k)); // decrescente
		}
		if(mx-mn == k) {
			vecmxmn[b].pb(k);
		}
		if(mx-k >= 0 && mx-k < n*m) {
			vecmx[b][mx-k].pb(k);
		}
		if(mn+k >= 0 && mn+k < n*m) {
			vecmn[b][mn+k].pb(k);
		}
	}
	reverse(all(mnB[b])); // (crescente,decrescente)
}

int query() {
	int mx0 = -inf;
	int mn0 = inf;
	int ans = 0;

	// m/B * 4 log
	for(int b = 0; b*B < n*m; b++) {
		int l = b*B;
		int r = min(n*m-1,(b+1)*B-1);

		auto itmx = upper_bound(all(mxB[b]),mp(mx0,inf));
		int posmx;
		if(itmx != mxB[b].end()) posmx = itmx->sc;
		else posmx = r+1;

		auto itmn = upper_bound(all(mnB[b]),mp(mn0,inf));
		int posmn;
		if(itmn != mnB[b].begin()) posmn = prev(itmn)->sc;
		else posmn = r+1;

		// depois de mudar os 2 -> max(posmn,posmx)
		ans+= vecmxmn[b].end() - lower_bound(all(vecmxmn[b]),max(posmn,posmx));

		if(posmx < posmn) {
			// posmx ate posmn-1
			// maxk - mn0 = k
			// maxk - k = mn0
			ans+= upper_bound(all(vecmx[b][mn0]),posmn-1) - lower_bound(all(vecmx[b][mn0]),posmx);
		}
		else if(posmn < posmx) {
			ans+= upper_bound(all(vecmn[b][mx0]),posmx-1) - lower_bound(all(vecmn[b][mx0]),posmn);
		}

		mn0 = min(mn0,mnB[b][0]);
		mx0 = max(mx0,mxb[b].back());
	}
	return ans;
}

void give_initial_chart(int32_t H, int32_t W, std::vector<int32_t> R, std::vector<int32_t> C) {
    n = H;
    m = W;
    for(int i = 0; i < n*m; i++) {
    	col[i] = C[i];
    	row[i] = R[i];
    }

    for(int i = 0; i*B < m; i++) {
    	construct(i);
    }
}

int32_t swap_seats(int32_t a, int32_t b) {
	swap(col[a],col[b]);
	construct(a/B); // B * log
	construct(b/B); // B * log
	return query(); // m/B * 4log
}

Compilation message

seats.cpp: In function 'long long int query()':
seats.cpp:83:26: error: no matching function for call to 'min(long long int&, __gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type&)'
   83 |   mn0 = min(mn0,mnB[b][0]);
      |                          ^
In file included from /usr/include/c++/10/vector:60,
                 from seats.h:3,
                 from seats.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
seats.cpp:83:26: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'})
   83 |   mn0 = min(mn0,mnB[b][0]);
      |                          ^
In file included from /usr/include/c++/10/vector:60,
                 from seats.h:3,
                 from seats.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
seats.cpp:83:26: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'})
   83 |   mn0 = min(mn0,mnB[b][0]);
      |                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from seats.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
seats.cpp:83:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   83 |   mn0 = min(mn0,mnB[b][0]);
      |                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from seats.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
seats.cpp:83:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   83 |   mn0 = min(mn0,mnB[b][0]);
      |                          ^
seats.cpp:84:17: error: 'mxb' was not declared in this scope; did you mean 'mx0'?
   84 |   mx0 = max(mx0,mxb[b].back());
      |                 ^~~
      |                 mx0
seats.cpp:57:7: warning: unused variable 'l' [-Wunused-variable]
   57 |   int l = b*B;
      |       ^