oj.uz

답안 #140630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140630 2019-08-03T22:13:32 Z silxikys 케이크 (CEOI14_cake) C++14
0 / 100
 1692 ms 44780 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;
    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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 214 ms 6136 KB Output isn't correct
2 Incorrect 188 ms 6268 KB Output isn't correct
3 Incorrect 211 ms 6264 KB Output isn't correct
4 Incorrect 199 ms 6264 KB Output isn't correct
5 Incorrect 262 ms 8556 KB Output isn't correct
6 Incorrect 234 ms 9004 KB Output isn't correct
7 Incorrect 238 ms 8740 KB Output isn't correct
8 Incorrect 219 ms 9080 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 483 ms 16860 KB Output isn't correct
2 Incorrect 319 ms 16880 KB Output isn't correct
3 Incorrect 294 ms 16632 KB Output isn't correct
4 Incorrect 2 ms 380 KB Output isn't correct
5 Incorrect 703 ms 39724 KB Output isn't correct
6 Incorrect 664 ms 39656 KB Output isn't correct
7 Incorrect 429 ms 39604 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 1272 KB Output isn't correct
2 Incorrect 73 ms 1616 KB Output isn't correct
3 Incorrect 223 ms 8856 KB Output isn't correct
4 Incorrect 187 ms 8792 KB Output isn't correct
5 Incorrect 148 ms 2028 KB Output isn't correct
6 Incorrect 474 ms 12108 KB Output isn't correct
7 Incorrect 252 ms 3960 KB Output isn't correct
8 Incorrect 225 ms 17392 KB Output isn't correct
9 Incorrect 1618 ms 44416 KB Output isn't correct
10 Incorrect 420 ms 5316 KB Output isn't correct
11 Incorrect 769 ms 8824 KB Output isn't correct
12 Incorrect 1507 ms 36732 KB Output isn't correct
13 Incorrect 1692 ms 44780 KB Output isn't correct