Submission #140630

#	Time	Username	Problem	Language	Result	Execution time	Memory
140630		silxikys	케이크 (CEOI14_cake)	C++14	0 / 100	1692 ms	44780 KiB

cake

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

/*
 * fast queries (few updates): 
 *      after each update, simply recompute all orders and 
 *      queries in O(1)
 *
 * fast updates (few queries):
 *      Give everyone enough space initally (5e5,2*5e5,3*5e5,...,10*5e5,10*5e5+1)
 *      Save each update, then before each query, recompute all orders and
 *      answer the query.
*/

const int maxn = 250005;
const int maxq = 5e5+5;
const ll INF = 1LL<<62;
int N, Q;
int d[maxn];
ll a[maxn];

struct Node {
	int s, e, m;
	//covers s,e;
	ll sum;
	ll mini;
    ll maxi;
	Node *l, *r;
	
	Node(int a, int b) {
		s = a;
		e = b;
		sum = INF;
		mini = INF;
        maxi = INF;
		if (s != e) {
			m = (s+e)/2;
			l = new Node(s,m);
			r = new Node(m+1,e);
		}
		else {
			l = NULL;
			r = NULL;
		}
	}


	void add(int i, ll x) {
		if (s == e) {
			sum = x;
			mini = sum;
            maxi = sum;
			return;
		}
		if (i <= m) {
			l->add(i,x);
		}
		else if (i > m) {
			r->add(i,x);
		}
		else assert(false);
		sum = l->sum + r->sum;
		mini = min(l->mini,r->mini);
        maxi = max(l->maxi,r->maxi);
	}

	ll getmini(int st, int en) {
		if (st <= s && e <= en) {
			return mini;
		}
		ll ret = INF;
		if (st <= m) {
			ret = min(ret,l->getmini(st,en));
		}
		if (en > m) {
			ret = min(ret,r->getmini(st,en));
		}
		return ret;
	}	

    ll getmaxi(int st, int en) {
		if (st <= s && e <= en) {
			return maxi;
		}
		ll ret = 0;
		if (st <= m) {
			ret = max(ret,l->getmaxi(st,en));
		}
		if (en > m) {
			ret = max(ret,r->getmaxi(st,en));
		}
		return ret;
	}
};

int start;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> start;
    vector<pair<int,int>> ps;
    for (int i = 1; i <= N; i++) {
        cin >> d[i];
        ps.push_back({d[i],i});
    }
    sort(ps.begin(),ps.end(),greater<pair<int,int>>());
    int t = 1;
    multiset<ll> ms;
    Node *root = new Node(1,N);
    for (auto p: ps) {
        a[p.second] = 1LL*t*maxq;
        root->add(p.second,a[p.second]);
        if (t <= 10) ms.insert(a[p.second]);
        t++;
    }

    /*
    for (int i = 1; i <= N; i++) {
        cout << i << ": " << root->getmini(i,i) << '\n';
    }
    */

    cin >> Q;
    while (Q--) {
        char c; cin >> c;
        if (c == 'E') { //update
            int i, e; cin >> i >> e;
            ll ai = -1;
            int j = 1;
            for (auto it = ms.begin(); it != ms.end(); ++it, j++) {
                if (j == e) {
                    //found it
                    ai = *it-Q;
                    /*
                    cout << "found " << ai << '\n';
                    cout << *it << '\n';
                    */
                    break;
                }
            }
            if (ms.count(a[i])) {
                ms.erase(a[i]);
            }
            else ms.erase(prev(ms.end()));
            a[i] = ai;
            ms.insert(ai);
            root->add(i,a[i]);

            /*
            for (int i = 1; i <= N; i++) {
                cout << i << ": " << root->getmini(i,i) << '\n';
            }
            cout << '\n';
            */
        }
        else { //query
            int b; cin >> b;
            if (b == start) {
                cout << 0 << '\n';
            }
            else if (b < start) {
                int c = start+1;
                int mn = root->getmini(b,start);
                for (int k = 17; k >= 0; k--) {
                    int nc = c+(1<<k);
                    if (nc > N) continue;
                    if (root->getmini(start+1,nc) > mn) {
                        c = nc;
                    }
                }
                int d = root->getmini(start+1,c) > mn ? c : start;
                //cout << b << ' ' << d << '\n';
                cout << (d-b) << '\n';
            }
            else {
                int c = start-1;
                int mn = root->getmini(start,b);
                for (int k = 17; k >= 0; k--) {
                    int nc = c-(1<<k);
                    if (nc < 1) continue;
                    if (root->getmini(nc,start-1) > mn) {
                        c = nc;
                    }
                }
                int d = root->getmini(c,start-1) > mn ? c : start;
                //cout  << d << ' ' << b << '\n';
                cout << (b-d) << '\n';
            }
        }
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50