Submission #228319

#	Time	Username	Problem	Language	Result	Execution time	Memory
228319		chctxdy68	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	315 ms	143864 KiB

shoes

                #include "shoes.h"
            	#include <bits/stdc++.h>
                #include <ext/pb_ds/assoc_container.hpp>
                #include <ext/pb_ds/tree_policy.hpp>
                #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
                #define ll long long
                #define ull unsigned long long
                #define ld long double
                #define pii pair <int, int>
                #define pll pair <ll, ll>
                #define pci pair <char, int>
                #define pld pair <ld, ld>
                #define ppld pair <pld, pld>
                #define ppll pair <pll, pll>
                #define pldl pair <ld, ll>
                #define vll vector <ll>
                #define vvll vector <vll>
                #define vpll vector <pll>
                #define pb push_back
                #define eb emplace_back
                #define mp make_pair
                #define fi first
                #define se second
                #define mll map <ll, ll>
                #define fastmap gp_hash_table
                #define cd complex <double>
                #define vcd vector <cd>
                #define PI 3.14159265358979
                #define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
                #pragma 03
                using namespace std;
                using namespace __gnu_pbds;
                queue <ll> rs[100005], ls[100005];
                ll st[800005];
                bool marked[200005];
                void update(ll root, ll l, ll r, ll i, ll val){
                	if (i < l || i > r) return;
                	if (l == r){
                		st[root] = val; return;
                	} 
                	ll mid = (l + r) / 2;
                	update(root * 2 + 1, l, mid, i, val);
                	update(root * 2 + 2, mid + 1, r, i, val);
                	st[root] = st[root * 2 + 1] + st[root * 2 + 2];
                }
                ll query(ll root, ll l, ll r, ll x, ll y){
                	if (y < l || x > r) return 0;
                	if (x <= l && y >= r) return st[root];
                	ll mid = (l + r) / 2;
                	return query(root * 2 + 1, l, mid, x, y) + query(root * 2 + 2, mid + 1, r, x, y);
                }
                ll count_swaps(vector <int> a){
                	for (ll i = 0; i < a.size(); i++){
                		if (a[i] < 0) ls[-a[i]].push(i);
                		else rs[a[i]].push(i);
                	}
                	ll ans = 0;
                	ll n = a.size();
                	for (ll i = 0; i < a.size(); i++) update(0, 0, n - 1, i, 1);
                	for (ll i = 0; i < a.size(); i++){
                		if (marked[i]) continue;
                		marked[i] = 1;
                		if (a[i] < 0){
                          	ls[-a[i]].pop();
                			ll p = rs[-a[i]].front(); rs[-a[i]].pop();
                			if (i + 1 <= p - 1) ans += query(0, 0, n - 1, i + 1, p - 1);
                			update(0, 0, n - 1, i, 0); update(0, 0, n - 1, p, 0);
                			marked[p] = 1;
                		}
                		else{
                          	rs[a[i]].pop();
                			ll p = ls[a[i]].front(); ls[a[i]].pop();
                			if (i + 1 <= p - 1) ans += query(0, 0, n - 1, i + 1, p - 1);
                          	ans++;
                			update(0, 0, n - 1, i, 0); update(0, 0, n - 1, p, 0);
                			marked[p] = 1;
                		}
                	}
                	return ans;
                }

Compilation message (stderr)

shoes.cpp:30:0: warning: ignoring #pragma 03  [-Wunknown-pragmas]
                 #pragma 03
 
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:53:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                  for (ll i = 0; i < a.size(); i++){
                                 ~~^~~~~~~~~~
shoes.cpp:59:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                  for (ll i = 0; i < a.size(); i++) update(0, 0, n - 1, i, 1);
                                 ~~^~~~~~~~~~
shoes.cpp:60:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                  for (ll i = 0; i < a.size(); i++){
                                 ~~^~~~~~~~~~

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