제출 #842365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842365		nasir_bashirov	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	442 ms	157420 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
 
// #define int long long
 
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define all(x) x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\
 
const int sz = 1e6 + 5;
ll t[sz * 4], lazy[sz * 4], n;
map<int, deque<int>> mp;
 
void push(int x, int lx, int rx){
	if(lx == rx or t[x] == 0)	return;
	t[x * 2] += lazy[x], t[x * 2 + 1] += lazy[x];
	lazy[x * 2] += lazy[x], lazy[x * 2 + 1] += lazy[x];
	lazy[x] = 0;
}
 
void build(int x, int lx, int rx){
	if(lx == rx){
		t[x] = lx;
		return;
	}
	int mid = (lx + rx) / 2;
	build(x * 2, lx, mid);
	build(x * 2 + 1, mid + 1, rx);
	t[x] = max(t[x * 2], t[x * 2 + 1]);
}
 
void update(int l, int r, int v, int x, int lx, int rx){
	push(x, lx, rx);
	if(lx >= l and rx <= r){
		t[x] += v;
		lazy[x] += v;
		return;
	}
	if(lx > r or l > rx)	return;
	int mid = (lx + rx) / 2;
	update(l, r, v, x * 2, lx, mid);
	update(l, r, v, x * 2 + 1, mid + 1, rx);
	t[x] = max(t[x * 2], t[x * 2 + 1]);
}
 
int query(int l, int r, int x, int lx, int rx){
	push(x, lx, rx);
	if(lx >= l and rx <= r)	  return t[x];
	if(lx > r or l > rx)	return 0;
	int mid = (lx + rx) / 2;
	return max(query(l, r, x * 2, lx, mid), query(l, r, x * 2 + 1, mid + 1, rx));
}
 
ll ind(int x){
	return query(x, x, 1, 1, n);
}
 
ll count_swaps(vi s) {
	n = s.size();
	vi used(n + 5, false);
	build(1, 1, n);
	ll res = 0;
	for(int i = 0; i < n; i++){
		ll indd = -1;
		if(!mp[-s[i]].empty())	 indd = mp[-s[i]].front();	
		// cout << i << " " << indd << endl;
		if(indd != -1){
			res += ind(i + 1) - ind(indd + 1) - (s[i] > 0 ? 1 : 0);
			// cout << "ind  " << ind(i + 1) << " " << ind(indd + 1) << endl;
			update(indd + 1, i, 1, 1, 1, n);
			mp[-s[i]].pop_front();
		}
		else{
			mp[s[i]].push_back(i);
		}
	}
	return res;
}
 
// signed main() {
// 	int n;
// 	cin >> n;
// 	vector<int> v(2 * n);
// 	for(int i = 0; i < 2 * n; i++){
// 		cin >> v[i];
// 	}
// 	cout << "input ended" << endl;
// 	cout << count_swaps(v) << endl;
// }

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15