Submission #1065191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065191		pan	Jousting tournament (IOI12_tournament)	C++17	100 / 100	185 ms	30088 KiB

tournament

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
using namespace __gnu_pbds;
#define ordered_set tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;

ll const INF = 1e13;

struct node{

    int s, e, m; 
    pi val; 
    ll lazy; 
    node *l, *r; 
    node (int S, int E)
    { 
       s = S, e = E, m = (s+e)/2;
       val = mp(0, -s);
       lazy = 0;
       l=r=nullptr;
 
    }
    void create()
    {
	    if(s != e && l==nullptr)
       { 
           l = new node(s, m); 
           r = new node(m+1, e); 
       }
    }
 
    void propogate()
    {
       if (lazy==0) return; 
       create();
       val.f+=lazy; 
       if (s != e){ 
           l->lazy+=lazy;
           r->lazy+=lazy;
       }
       lazy=0; 
    }
  void update(int S, int E, ll V)
  { 
	      propogate();
       if(s==S && e==E) lazy += V; 
       else{ 
           create();
           if(E <= m) l->update(S, E, V); 
           else if (m < S) r->update(S, E, V); 
           else l->update(S, m, V),r->update(m+1, E, V);
           l->propogate(),r->propogate();
           val = max(l->val, r->val); 
       }
    }
    pi query(int S, int E)
    {

       propogate(); 
       if(s == S && e == E) return val; 
       create();
       if(E <= m) return l->query(S, E); 
       else if(S >= m+1) return r->query(S, E); 
       else return max(l->query(S, m), r->query(m+1, E)); 
   }

} *root1, *root2;
 




int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
  ll n = N;
  ordered_set dis;
  for (ll i=0; i<n; ++i) dis.insert(mp(i, i));
  vector<pi> realq;
  for (ll i=0; i<C; ++i)
  {
    ll l = LLONG_MAX, r = LLONG_MIN;
    for (ll j=S[i]; j<=E[i]; ++j)
    {
      auto now = dis.find_by_order(S[i]);
      l = min(l, now->f);
      r = max(r, now->s);
      dis.erase(now);
    }
    realq.pb(mp(l, r));
    dis.insert(mp(l, r));
  }
  pi ans = mp(0, 0);
  root1 = new node(0, n-2);
  root2 = new node(0, n-1);
  for (ll i=0; i<n-1; ++i) root1->update(i, i, K[i]);
  for (pi u: realq)
  {
    pi maxx = root1->query(u.f, u.s-1);
    if (maxx.f > R) root2->update(u.f, u.s, -INF);
    else root2->update(u.f, u.s, 1);
    ans = max(ans, root2->query(0, n-1));
  }

	return ans.s*-1LL;
}

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