oj.uz

Submission #140633

# Submission time Handle Problem Language Result Execution time Memory
140633 2019-08-03T22:57:15 Z silxikys Cake (CEOI14_cake) C++14
0 / 100
 1880 ms 38428 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);
                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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 1656 KB Output is correct
2 Incorrect 190 ms 1784 KB Output isn't correct
3 Correct 249 ms 1856 KB Output is correct
4 Correct 143 ms 1784 KB Output is correct
5 Correct 358 ms 3960 KB Output is correct
6 Incorrect 285 ms 3964 KB Output isn't correct
7 Correct 255 ms 3960 KB Output is correct
8 Correct 161 ms 3960 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 15468 KB Output is correct
2 Incorrect 262 ms 15596 KB Output isn't correct
3 Incorrect 257 ms 15444 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Correct 583 ms 37388 KB Output is correct
6 Correct 614 ms 37352 KB Output is correct
7 Incorrect 434 ms 37376 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 1016 KB Output isn't correct
2 Incorrect 73 ms 1176 KB Output isn't correct
3 Incorrect 218 ms 7796 KB Output isn't correct
4 Incorrect 194 ms 7796 KB Output isn't correct
5 Incorrect 163 ms 992 KB Output isn't correct
6 Incorrect 414 ms 10256 KB Output isn't correct
7 Incorrect 253 ms 2296 KB Output isn't correct
8 Correct 221 ms 14960 KB Output is correct
9 Incorrect 1880 ms 38428 KB Output isn't correct
10 Incorrect 540 ms 1784 KB Output isn't correct
11 Incorrect 862 ms 4676 KB Output isn't correct
12 Correct 1806 ms 31020 KB Output is correct
13 Correct 1607 ms 38320 KB Output is correct