Submission #371409

#	Time	Username	Problem	Language	Result	Execution time	Memory
371409		leinad2	The Big Prize (IOI17_prize)	C++17	20 / 100	3085 ms	7288 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int A[200010];
vector<int>B[200010];
int seg[800010];
void update(int id, int s, int e, int x, int v)
{
    if(e<x||x<s)return;
    if(s==e)
    {
        seg[id]+=v;
        return;
    }
    int m=s+e>>1;
    update(id*2, s, m, x, v);update(id*2+1, m+1, e, x, v);
    seg[id]=seg[id*2]+seg[id*2+1];
}
int get(int id, int s, int e, int l, int r)
{
    if(e<l||r<s)return 0;
    if(l<=s&&e<=r)return seg[id];
    int m=s+e>>1;
    return get(id*2, s, m, l, r)+get(id*2+1, m+1, e, l, r);
}
int find_best(int n)
{
    while(1)
    {
        int a=0, b=n-1;
        while(a<b)
        {
            int m=a+b>>1;
            vector<int>v;
            if(B[m].size())v=B[m];
            else v=ask(m);
            B[m]=v;
            if(v[0]+v[1]==0)return m;
            if(v[1]>get(1, 1, n, 1, m+1))a=m+1;
            else b=m;
        }
        vector<int>v;
        if(B[a].size())v=B[a];
        else v=ask(a);
        B[a]=v;
        if(v[0]+v[1]==0)return a;
        update(1, 1, n, 1, 1);update(1, 1, n, a+1, -1);
    }
}

Compilation message (stderr)

prize.cpp: In function 'void update(int, int, int, int, int)':
prize.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     int m=s+e>>1;
      |           ~^~
prize.cpp: In function 'int get(int, int, int, int, int)':
prize.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int m=s+e>>1;
      |           ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:33:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |             int m=a+b>>1;
      |                   ~^~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80