oj.uz

Submission #140634

# Submission time Handle Problem Language Result Execution time Memory
140634 2019-08-03T23:14:45 Z silxikys Cake (CEOI14_cake) C++14
100 / 100
 1845 ms 38492 KB 
#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;
	Node *l, *r;
	
	Node(int a, int b) {
		s = a;
		e = b;
		sum = INF;
		mini = 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;
			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);
	}

	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;
	}	
};

int start;
vector<int> v;

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;
    Node *root = new Node(1,N);
    for (auto p: ps) {
        a[p.second] = t;
        root->add(p.second,t);
        if (t <= 15) v.push_back(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;
            e--;
            int curr = v[e];
            a[i] = a[curr]-1;
            root->add(i,a[i]);
            for (int j = 0; j < e; j++) {
                root->add(v[j],a[v[j]]-1); //decrement by 1
                a[v[j]]--;
            }

            auto it = find(v.begin(),v.end(),i);
            if (it != v.end()) v.erase(it);
            v.insert(v.begin()+e,i);
            if (v.size() > 15) v.pop_back();
            /*
            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-1);
                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+1,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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 23 ms 1784 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 1700 KB Output is correct
2 Correct 183 ms 1884 KB Output is correct
3 Correct 240 ms 1912 KB Output is correct
4 Correct 142 ms 1912 KB Output is correct
5 Correct 357 ms 3960 KB Output is correct
6 Correct 283 ms 3960 KB Output is correct
7 Correct 257 ms 3960 KB Output is correct
8 Correct 159 ms 3960 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 15596 KB Output is correct
2 Correct 312 ms 15344 KB Output is correct
3 Correct 282 ms 15188 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 619 ms 37236 KB Output is correct
6 Correct 647 ms 37224 KB Output is correct
7 Correct 428 ms 37096 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 888 KB Output is correct
2 Correct 73 ms 1272 KB Output is correct
3 Correct 222 ms 7824 KB Output is correct
4 Correct 195 ms 7964 KB Output is correct
5 Correct 164 ms 1120 KB Output is correct
6 Correct 409 ms 10324 KB Output is correct
7 Correct 252 ms 2552 KB Output is correct
8 Correct 215 ms 14852 KB Output is correct
9 Correct 1845 ms 38376 KB Output is correct
10 Correct 545 ms 1912 KB Output is correct
11 Correct 884 ms 4680 KB Output is correct
12 Correct 1839 ms 31080 KB Output is correct
13 Correct 1614 ms 38492 KB Output is correct