Submission #945984

#	Time	Username	Problem	Language	Result	Execution time	Memory
945984		kxd	Jousting tournament (IOI12_tournament)	C++17	0 / 100	1080 ms	168432 KiB

tournament

#include <bits/stdc++.h>
//#define DEBUG 1106
//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<int,int>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif

using namespace std;
const int N = 2e5+5;
const int inf = 1e9;
//const int INF = 1e18;
const int MOD = 1e9+7;

struct node {
    int s, e, m, v;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, v = inf;
        m = (s+e)/2;
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    int query(int a, int b) {
        if(a <= s && e <= b) return v;
        else if(a > m) return r->query(a, b);
        else if(b <= m) return l->query(a, b);
        else return min(l->query(a, b), r->query(a, b));
    }
    void up(int p, int val) {
        if(s == e) {
            v = val; return;
        } else if(p <= m) l->up(p, val);
        else r->up(p, val);
        v = min(l->v, r->v);
    }
} *root;

struct node2 {
    int s, e, m, v;
    int lazy; //lazy value storage
    node2 *l, *r;
    node2(int _s, int _e) {
        s = _s;
        e = _e;
        v = lazy = 0;
        if (s == e) return;
        m = (s + e) / 2;
        //Do not create the children here
        l = r = nullptr;
    }
    void chode() {
		if (s != e && l == nullptr) {
        	l = new node2(s, m);
        	r = new node2(m+1, e);
		}
	}
    void propo() { 
        //Create before propo
        chode();
        if (lazy != 0) {
            //Update value base on range
            v += lazy * (e - s + 1);
            //Propogate
            if (s != e) {
                r -> lazy += lazy;
                l -> lazy += lazy;
            }
            lazy = 0;
        }
    }
    void up(int x, int y, int c) {
        chode();
        //Propo before update
        if (s >= x && e <= y) {
            lazy += c;
            return;
        } else {
        	propo();
            if (y <= m) l -> up(x, y, c);
            else if (x > m) r -> up(x, y, c);
            else {
				l -> up(x, y, c);
				r -> up(x, y, c);
			}
            //Reminder to propo before updating cur node2 value
            l -> propo(); r -> propo();
            v = l -> v + r -> v;
        }
    }
    int query(int x, int y) {
        propo();
        if (s >= x && e <= y) return v;
        if (x > m) return r -> query(x, y);
        if (y <= m) return l -> query(x, y);
        else return l -> query(x, y) + r -> query(x, y);
    }
	int search(int x) {
		if (s==e) return s;
		chode();
		if (l->v>=x) return l->search(x);
		else return r->search(x-(l->v));
	}
} *root2;

int a[N];

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
	root = new node(0,n);
	forn1(i,n-1) {
		a[i] = k[i];
		root->up(i,a[i]);
	}
	a[0]=r;
	root->up(0,a[0]);
	int ans = 0;
	int val = -1;
	forn(i,n) {
		root2 = new node2(0,n);
		root2->up(0,n-1,1);
		if(i) {
			swap(a[i],a[i-1]);
			root->up(i,a[i]);
			root->up(i-1,a[i-1]);
		}
		int loc = i;
		int rd = 0;
		forn(j,c) {
			int st = root2->search(s[i]);
			int ed = root2->search(e[i]);
			int win = root->query(st,ed);
			if(st<=loc && loc<=ed) {
				rd++;
				if(r<=win) break;
				loc = st;
				root2->up(st,ed,-1);
				root2->up(st,st,1);
			} else {
				if(ed<loc) loc -= (ed-st);
				root2->up(st,ed,-1);
				root2->up(st,st,1);
			}
		}
		if(rd>val) ans = i, val = rd;
	}
	return ans;
}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int main() {
  int tmp;

  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}
*/

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51