Submission #741548

#	Time	Username	Problem	Language	Result	Execution time	Memory
741548		LCJLY	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	249 ms	134732 KiB

shoes

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

typedef pair<int,int>pii;

typedef long long ll;
struct node {
    int s, e;
    ll mn, mx, sum;
    bool lset;
    ll add_val, set_val;
    node *l, *r;
    node (int _s, int _e, int A[] = NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL) {
        if (A == NULL) return;
        if (s == e) mn = mx = sum = A[s];
        else {
            l = new node(s, (s+e)>>1, A), r = new node((s+e+2)>>1, e, A);
            combine();
        }
    }
    void create_children() {
        if (s == e) return;
        if (l != NULL) return;
        int m = (s+e)>>1;
        l = new node(s, m);
        r = new node(m+1, e);
    }
    void self_set(ll v) {
        lset = 1;
        mn = mx = set_val = v;
        sum = v * (e-s+1);
        add_val = 0;
    }
    void self_add(ll v) {
        if (lset) { self_set(v + set_val); return; }
        mn += v, mx += v, add_val += v;
        sum += v*(e-s+1);
    }
    void lazy_propagate() {
        if (s == e) return;
        if (lset) {
            l->self_set(set_val), r->self_set(set_val);
            lset = set_val = 0LL;
        }   
        if (add_val != 0) {
            l->self_add(add_val), r->self_add(add_val);
            add_val = 0;
        }
    }
    void combine() {
        if (l == NULL) return;
        sum = l->sum + r->sum;
        mn = min(l->mn, r->mn);
        mx = max(l->mx, r->mx);
    }
    void add(int x, int y, ll v) {
		if(x>y) return;
        if (s == x && e == y) { self_add(v); return; }
        int m = (s+e)>>1;
        create_children(); lazy_propagate();
        if (x <= m) l->add(x, min(y, m), v);
        if (y > m) r->add(max(x, m+1), y, v);
        
        combine();
    }
    void set(int x, int y, ll v) {
        if (s == x && e == y) { self_set(v); return; }
        int m = (s+e)>>1;
        create_children(); lazy_propagate();
        if (x <= m) l->set(x, min(y, m), v);
        if (y > m) r->set(max(x, m+1), y, v);
        combine();
    }
    ll range_sum(int x, int y) {
        if (s == x && e == y) return sum;
        if (l == NULL || lset) return (sum / (e-s+1)) * (y-x+1);
        int m = (s+e)>>1;
        lazy_propagate();
        if (y <= m) return l->range_sum(x, y);
        if (x > m) return r->range_sum(x, y);
        return l->range_sum(x, m) + r->range_sum(m+1, y);
    }
    ll range_min(int x, int y) {
        if (s == x && e == y) return mn;
        if (l == NULL || lset) return mn;
        int m = (s+e)>>1;
        lazy_propagate();
        if (y <= m) return l->range_min(x, y);
        if (x > m) return r->range_min(x, y);
        return min(l->range_min(x, m), r->range_min(m+1, y));
    }
    ll range_max(int x, int y) {
        if (s == x && e == y) return mx;
        if (l == NULL || lset) return mx;
        int m = (s+e)>>1;
        lazy_propagate();
        if (y <= m) return l->range_max(x, y);
        if (x > m) return r->range_max(x, y);
        return max(l->range_max(x, m), r->range_max(m+1, y));
    }
    ~node() {
        if (l != NULL) delete l;
        if (r != NULL) delete r;
    }
} *root;

long long count_swaps(vector<int> s) {
	//cout << "check\n";
	//int cnt[100005];
	//memset(cnt,0,sizeof(cnt));
	int n=s.size();
	vector<int>r[10*n+5]; //cnt<0
	vector<int>l[10*n+5];
	//cout << "check\n";

	
	root = new node(0,10*n+5);
	
	for(int x=n-1;x>=0;x--){
		if(s[x]>0){
			//right
			r[s[x]].push_back(x);
		}
		else{
			//left
			l[abs(s[x])].push_back(x);
		}
	}
	
	long long counter=0;
	for(int x=0;x<n;x++){
		int target;
		if(s[x]>0){
			if(r[s[x]].empty()||r[s[x]].back()!=x) continue;
			r[s[x]].pop_back();
			if(l[s[x]].empty()) continue;
			target=l[s[x]].back();
			int target2=target;
			target+=root->range_sum(target,target);
			int cur=x+root->range_sum(x,x);
			l[s[x]].pop_back();
			int dist=abs(cur-target);
			counter+=dist;
			root->add(x+1,target2,1);
		}
		else{
			if(l[-s[x]].empty()||l[-s[x]].back()!=x) continue;
			l[-s[x]].pop_back();
			if(r[-s[x]].empty()) continue;
			target=r[-s[x]].back();
			int target2=target;
			target+=root->range_sum(target,target);
			int cur=x+root->range_sum(x,x);
			r[-s[x]].pop_back();
			int dist=abs(cur-target)-1;
			counter+=dist;
			root->add(x+1,target2,1);
		}
		//cout << counter << "\n";
	}
	//cout << counter << " check\n";
	return counter;
}

Compilation message (stderr)

shoes.cpp: In member function 'void node::lazy_propagate()':
shoes.cpp:44:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   44 |             lset = set_val = 0LL;
      |                    ~~~~~~~~^~~~~

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