Submission #1085181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085181		yeediot	Teams (IOI15_teams)	C++17	0 / 100	438 ms	370636 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
#define ll long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
const int mxn = 5e5 + 5;
ll cnt, rt[mxn];
struct segtree{
    struct nde{
        int l, r;
        ll c;
    }seg[mxn << 5];
    #define x seg[node]
    ll build(int l, int r){
        int node = ++cnt;
        seg[node].c = 0;
        if(l == r){
            return node;
        }
        int mm = l + r >> 1;
        x.l = build(l, mm), x.r = build(mm + 1, r);
        return node;
    }
    ll ins(int from, int l, int r, int p){
        int node = ++cnt;
        seg[node] = seg[from];
        if(l == r){
            seg[node].c++;
            return node;
        }
        int mm = l + r >> 1;
        if(p <= mm){
            x.l = ins(x.l, l, mm, p);
        }
        else{
            x.r = ins(x.r, mm + 1, r, p);
        }
        x.c = seg[x.l].c + seg[x.r].c;
        return node;
    }
    ll kth(int v, int u, int l, int r, int k){
        if(l == r){
            return l;
        }
        int mm = l + r >> 1;
        ll cc = seg[seg[v].r].c - seg[seg[u].r].c;
        if(k > cc){
            return kth(seg[v].l, seg[u].l, l, mm, k - cc);
        }
        else{
            return kth(seg[v].r, seg[u].r, mm + 1, r, k);
        }
    }
    ll bs(int v, int u, int l, int r, int k){
        if(l == r){
            return seg[v].c - seg[u].c;
        }
        int mm = l + r >> 1;
        if(k > mm){
            return bs(seg[v].r, seg[u].r, mm + 1, r, k);
        }
        else{
            return bs(seg[v].l, seg[u].l, l, mm, k) + seg[seg[v].r].c - seg[seg[u].r].c; 
        }
    }
}tr;
int n;
void init(int N, int a[], int b[]){
    n = N;
    rt[0] = tr.build(1, n);
    vector<pair<ll, ll>>pt;
    for(int i = 0; i < n; i++){
        pt.pb({a[i], b[i]});
    }
    sort(all(pt));
    ll pos = 0;
    for(int i = 1; i <= n; i++){
        rt[i] = rt[i - 1];
        for(; pos < n and pt[pos].F == i; pos++){
            tr.ins(rt[i], 1, n, pt[pos].S);
        }
    }
}
int can(int m, int K[]){
    vector<array<ll, 3>>st;
    vector<ll>k;
    for(int i = 0; i < m; i++) k.pb(K[i]);
    st.pb({0LL, 0LL, 0LL});
    sort(all(k));
    for(auto i : k){
        while(sz(st) and st.back()[1] < i){
            st.pop_back();
        }
        ll tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
        if(tot < 0){
            return false;
        }
        ll cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
        while(sz(st) and cur > st.back()[1]){
            st.pop_back();
            cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
        }
        st.pb({i, cur, tot});
    }
    return true;
}

Compilation message (stderr)

teams.cpp: In member function 'long long int segtree::build(int, int)':
teams.cpp:28:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   28 |         int node = ++cnt;
      |                    ^~~~~
teams.cpp:33:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp:34:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |         x.l = build(l, mm), x.r = build(mm + 1, r);
      |               ~~~~~^~~~~~~
teams.cpp:34:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |         x.l = build(l, mm), x.r = build(mm + 1, r);
      |                                   ~~~~~^~~~~~~~~~~
teams.cpp: In member function 'long long int segtree::ins(int, int, int, int)':
teams.cpp:38:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   38 |         int node = ++cnt;
      |                    ^~~~~
teams.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp:46:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |             x.l = ins(x.l, l, mm, p);
      |                   ~~~^~~~~~~~~~~~~~~
teams.cpp:49:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |             x.r = ins(x.r, mm + 1, r, p);
      |                   ~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'long long int segtree::kth(int, int, int, int, int)':
teams.cpp:58:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp:61:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |             return kth(seg[v].l, seg[u].l, l, mm, k - cc);
      |                                                   ~~^~~~
teams.cpp: In member function 'long long int segtree::bs(int, int, int, int, int)':
teams.cpp:71:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:93:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |             tr.ins(rt[i], 1, n, pt[pos].S);
      |                    ~~~~^
teams.cpp:6:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    6 | #define S second
teams.cpp:93:41: note: in expansion of macro 'S'
   93 |             tr.ins(rt[i], 1, n, pt[pos].S);
      |                                         ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:107:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |         ll tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
      |                                       ~~~~^
teams.cpp:107:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |         ll tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
      |                                              ~~~~~~~~~~~~~~~^
teams.cpp:107:70: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |         ll tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
      |                                                                      ^
teams.cpp:111:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |         ll cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
      |                         ~~~~^
teams.cpp:111:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |         ll cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
      |                                ~~~~~~~~~~~~~~~^
teams.cpp:111:60: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |         ll cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
teams.cpp:114:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |             cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
      |                          ~~~~^
teams.cpp:114:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |             cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
      |                                 ~~~~~~~~~~~~~~~^
teams.cpp:114:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |             cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23