Submission #780593

#	Time	Username	Problem	Language	Result	Execution time	Memory
780593		caganyanmaz	Teams (IOI15_teams)	C++17	0 / 100	2982 ms	136800 KiB

teams

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define mp(x...) array<int, 2>({x})
#include "teams.h"

constexpr static int DEBUG_SIZE = 10;

void __print(const char* s) { cerr << s; }
void __print(string s) { cerr << s; }
void __print(int* i) { cerr << "{"; cerr << i[0]; for (int j = 1; j < DEBUG_SIZE; j++) cerr << ", " << i[j]; cerr << "}"; }
void __print(int i) { cerr << i; }
template<typename T>
void __print(T& t) {cerr <<"{";int f = 0; for (auto& i : t) { cerr << ((f++) ?  ", ": ""); __print(i); } cerr <<"}";}
void _print() { cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if(sizeof...(v)) cerr << ", "; _print(v...); }
//#define DEBUGGING
#ifdef DEBUGGING
#define debug(x...) cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...)
#endif

constexpr static int MXSIZE = 1000000;
constexpr static int MXSEG = 10000000;
int n, st[MXSEG], l[MXSEG], r[MXSEG];
array<int, 2> intervals[MXSIZE];
array<int, 2> updates[MXSIZE+1];
int last = 1;

int query(int ll, int rr, int index, int ss, int ee)
{
        if (ll >= ee || ss >= rr || index == -1)
                return 0;
        if (ee >= rr && ll >= ss)
                return st[index];
        int m = ll+rr>>1;
        int lres = query(ll, m, l[index], ss, ee);
        int rres = query(m, rr, r[index], ss, ee);
        return lres + rres;
}

int update(int ll, int rr, int index, int i, int val)
{
        if (ll + 1 == rr)
        {
                st[last] = val;
                return last++;
        }
        int m = ll+rr>>1;
        int lindex, rindex;
        if (i < m)
        {
                lindex = update(ll, m, l[index], i, val);
                rindex = (index == -1) ? -1 : r[index];
        }
        else
        {
                lindex = (index == -1) ? -1 : l[index];
                rindex = update(m, rr, r[index], i, val);
        }
        l[last] = lindex;
        r[last] = rindex;
        st[last] = (lindex == -1) ? 0 : st[lindex];
        st[last] += (rindex == -1) ? 0 : st[rindex];
        return last++;
}

void config_st()
{
        l[0] = r[0] = -1;
}

void init(int N, int A[], int B[])
{
        n = N;
        for (int i = 0; i < n; i++)
                intervals[i] = mp(A[i], B[i]);
        sort(intervals, intervals + n);
        int last_root = 0;
        updates[0] = mp(0, 0);
        for (int i = 0; i < n; i++)
        {
                int old_count = query(0, n, last_root, intervals[i][1]-1, intervals[i][1]);
                int new_root = update(0, n, last_root, intervals[i][1]-1, old_count+1);
                updates[i+1] = mp(intervals[i][0], new_root);
                debug(i+1, intervals[i][0], new_root);
                last_root = new_root;
        }
}

int can(int m, int k[])
{
        sort(k, k+m);
        vector<array<int, 3>> stck; // Root, ending, additional (if at there are some free left in the ending)
        for (int i = 0; i < m; i++)
        {
                int current_index = upper_bound(updates, updates + n, mp(k[i] + 1, -1)) - updates;
                if (k[i] + 1 > updates[current_index][0])
                        current_index++;
                if (!current_index)
                        return 0;
                current_index--;
                int current_root = updates[current_index][1];
                debug(k[i], current_root, updates[current_index-1][0]);
                int current_val = k[i];
                int last_l = k[i];
                while (stck.size())
                {
                        int prev_used = query(0, n, end(stck)[-1][0], last_l, end(stck)[-1][1]) - end(stck)[-1][2];
                        current_val += prev_used;
                        int current_available = query(0, n, current_root, last_l, end(stck)[-1][1]);
                        if (current_val <= current_available)
                                break;
                        current_val -= current_available;
                        last_l = end(stck)[-1][1];
                        stck.pop_back();
                }
                int ending = n+1;
                if (stck.size())
                        ending = end(stck)[-1][1]+1;
                int ll = last_l, rr = ending;
                while (rr - ll > 1)
                {
                        int m = ll+rr>>1;
                        if (query(0, n, current_root, last_l, m) >= current_val)
                                rr = m;
                        else
                                ll = m;
                }
                if (rr == ending)
                        return 0;
                debug(current_root, last_l, rr, query(0, n, current_root, last_l, rr), query(0, n, current_root, 0, n));
                stck.pb({current_root, rr, query(0, n, current_root, last_l, rr) - current_val});

        }
        return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:38:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int m = ll+rr>>1;
      |                 ~~^~~
teams.cpp: In function 'int update(int, int, int, int, int)':
teams.cpp:51:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int m = ll+rr>>1;
      |                 ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:99:89: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   99 |                 int current_index = upper_bound(updates, updates + n, mp(k[i] + 1, -1)) - updates;
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
teams.cpp:126:29: warning: declaration of 'int m' shadows a parameter [-Wshadow]
  126 |                         int m = ll+rr>>1;
      |                             ^
teams.cpp:93:13: note: shadowed declaration is here
   93 | int can(int m, int k[])
      |         ~~~~^
teams.cpp:126:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |                         int m = ll+rr>>1;
      |                                 ~~^~~

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