To find the shortest path from point O to lines AB and CD (in that order) one needs to consider three possibilities, namely projection from O to CD (if it intersects AB); projection on CD of the reflection of O thru AB (if it intersects AB); intersection of AB and CD.

#include <bits/stdc++.h>
using namespace std;

int query(int l, int r, vector<int> bucket, vector<int> v) {
    int n = v.size();
    int bkt_sz = sqrt(n);
    int bkts = bucket.size();

    int lb = l/bkt_sz;
    int rb = r/bkt_sz;
    int lbp = l%bkt_sz;
    int rbp = r%bkt_sz;


    int retval = -1;

    if (lb == rb) {
        for (int i=lb*bkt_sz+lbp; i <= lb*bkt_sz+rbp; i++)
            retval = max(retval, v[i]);
        return retval;
    }

    for (int i=lb+1; i < rb; i++)
        retval = max(retval, bucket[i]);

    for (int i=lb*bkt_sz+lbp; i<n; i++) {
        if (i >= (lb+1)*bkt_sz) break;
        retval = max(retval, v[i]);
    }

    for (int i=rb*bkt_sz; i <= rb*bkt_sz+rbp; i++) {
        retval = max(retval, v[i]);
    }

    return retval;
}

int main() {

    int k;
    cin >> k;

    vector<int> v;

    while (true) {
        int a;
        cin >> a;
        if (a == -1) break;
        v.push_back(a);
    }

    int n = v.size();
    int bkt_sz = sqrt(n);

    vector<int> bucket;

    int count = bkt_sz;
    int max_value = -1;
    for (int i=0; i<n; i++) {
        if (count == 0) {
            count = bkt_sz;
            bucket.push_back(max_value);
            max_value = -1;
        }
        count -= 1;
        max_value = max(max_value, v[i]);
    }

    bucket.push_back(max_value);

    for (int i=0; i+k-1 < n; i++) {
        cout << query(i, i+k-1, bucket, v) << endl;
    }

}

Edited by author 19.04.2018 22:19

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication8
{
    class Program
    {
        static void Main(string[] args)
        {
            int x;
            x = Convert.ToInt32 (Console.ReadLine());
            if ((x > 1 & x <= 4)
            {
                Console.WriteLine("few");
            }
            if (x > 5 & x<= 9)
            {
                Console.WriteLine("several");
            }
            if (x > 10 & x <= 19)
            {
                Console.WriteLine("pack");
            }
            if (x > 20 & x <= 49)
            {
                Console.WriteLine("lots");
            }
            if (x > 50 & x <= 99)
            {
                Console.WriteLine("horde");
            }
            if (x > 100 & x <= 249)
            {
                Console.WriteLine("throng");
            }
            if (x > 250 & x <= 499)
            {
                Console.WriteLine("swarm");
            }
            if (x > 500 & x <= 499)
            {
                Console.WriteLine("zounds");
            }
            if (x > 1000)
            {
                Console.WriteLine("legion");
            }
        }
    }
}

Да что тут не так?

Edited by author 18.04.2018 23:36

Edited by author 18.04.2018 23:37

there is O(n*m) D&C algorithm...  similar with ural 1674 and ural 1596

it is just extend of fermat point, the angle is 2*pi/3 if it is fermat point in this problem

three angles are  acos((c1*c1-c2*c2-c3*c3)/(2*c2*c3)),acos((c2*c2-c1*c1-c3*c3)/(2*c1*c3) and

acos((c3*c3-c1*c1-c2*c2)/(2*c1*c2))

how to get it ,just let two partial derivative to be zero,and square and add two equtation we can get it ,it is easy

Edited by moderator 23.08.2020 01:12

there is a line which isn't token "end" and has no ':' character and there is only one nonempty token..
I use OLE test it must be wrong test...

Unfortunately, std::string in C++ class is very slow...

use N = 100001 instead N = 100000

Solution is a sum( [ sqrt(2*i*R - i^2) ], i = 1,2,...,R), where [ x ] - round to up.

But, I always GOT TL on 17 test).

Consider 2D problem in polar coordinates: intersect disk with given radius R and center in the origin with triangle with vertexes in origin, (R1,0), and (R2,phi). Solve it using quadratic equation... Combine the algebraic sum of solutions to get the final result.

Edited by author 12.04.2018 22:45

Check: SBT; SAT, SABT, SBAT, SACT; the same four with swapped A and C

33
1 2 5 6 4 4 5 2 1 6
2 2 4 3 1 3 3 3 3 1
2 1 4 4 3 2 4 3 1 4
1 1 3 3 0 2 2 2 2 0
2 2 6 1 -1 1 5 6 5 0
2 2 0 3 -1 1 5 6 5 0
2 2 -4 0 -1 1 5 6 5 0
2 2 6 7 -1 1 5 6 5 0
2 2 5 7 -1 1 4 6 5 0
1 1 6 6 2 2 3 3 4 4
1 1 6 6 2 4 3 3 4 2
1 1 2 2 -1 -1 -1 -2 -2 -1
1 1 3 3 4 6 2 2 6 4
1 1 3 3 4 6 1 2 6 4
1 1 3 3 4 6 1 2 7 4
1 1 2 2 1 3 3 3 3 1
1 1 1 5 0 8 1 2 3 2
5 2 3 5 -1 2 4 5 6 3
4 1 5 5 2 3 6 4 5 2
1 1 7 5 2 3 6 4 5 2
1 1 3 3 2 4 2 2 4 2
6 1 6 4 0 5 7 2 6 5
2 2 4 2 2 1 3 6 4 1
4 2 2 2 2 1 3 6 4 1
8 7 1 3 6 1 7 4 0 9
5 1 2 2 2 1 4 1 8 9
9 -1 3 1 0 0 7 0 3 3
1 -1 6 7 0 0 7 0 3 3
0 0 8 0 2 0 4 0 6 0
1 1 4 4 0 3 3 3 3 0
0 0 0 4 2 1 0 2 2 3
0 0 0 4 0 2 2 2 3 2
1 1 5 2 1 2 5 1 0 3

8.000000
3.650282
3.828427
4.576491
5.019765
5.398346
6.324555
10.676619
10.605551
7.071068
7.634414
1.414214
8.993230
8.993230
9.162278
1.414214
5.841619
5.242641
5.064495
7.621233
4.576491
5.576491
4.000000
4.000000
11.709720
4.000000
9.211103
10.633758
8.000000
6.359174
4.000000
4.000000
5.000000

I do not understand why, but my program gives
different result, than sample.

in this picture, i draw a figure with yellow,
i think area of this figure is an answer, i am right ?
download this picture:
http://slil.ru/28091271

Does anyone know the input for test 7?

The time limit for the problem has been corrected from 2.0 sec to 1.0 sec. The new value better reflects the original expectations for accepted solutions back from 2006. Around 40 authors have lost their AC (mostly submitted since 2017).

just print the max sum of three consecutive numbers and also the index of the middle element of the numbers.

If there is a way to improve, let me know:

#ifdef __MINGW32__
#define uputchar _putchar_nolock
#define ugetchar _getchar_nolock
#define ufread _fread_nolock
#define funlock _unlock_file
#else
#define uputchar putchar_unlocked
#define ugetchar getchar_unlocked
#define ufread fread_unlocked
#define funlock funlockfile
#endif

namespace
{

#if 1
struct
{

    int c;
    int operator * () const { return c; }
    auto & operator ++ () { c = ugetchar(); return *this; }
    auto operator ++ (int) { auto prev = *this; operator ++ (); return prev; }

} cursor;
#else
char input[(1 << 21) + (1 << 19)];
auto cursor = input;
auto input_size = cursor - input;
#endif

inline
void skip_ws()
{
    for (;;) {
        switch (*++cursor) {
        case ' ' :
        case '\t' :
        case '\r' :
        case '\n' :
            break;
        default :
            return;
        }
    }
}

inline
void read_input()
{
    //std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
#if 0
#ifdef ONLINE_JUDGE
    cursor += ufread(input, sizeof(char), sizeof input, stdin);
#else
    {
        const char s[] = R"(4
                         0 0
                         1 0
                         0 1
                         1 2
                         2
                         0 0
                         0 2)";
        cursor = std::copy(s, s + sizeof s - 1, cursor);
    }
#endif
    //assert(cursor < input + sizeof input);
    //assert(input + 0 != nullptr);
    input_size = cursor - input;
    cursor = input - 1;
#endif
}

template< typename U >
void read_uint(U & u)
{
    static_assert(std::is_unsigned< U >::value, "!");
    u = 0;
    for (;;)  {
        char c = *cursor;
        if ((c < '0') || ('9' < c)) {
            break;
        }
        ++cursor;
        u = (u * 10) + (c - '0');
    }
}

template< typename I >
void read_int(I & i)
{
    char sign = *cursor;
    switch (sign) {
    case '+' :
    case '-' :
        ++cursor;
    }
    std::make_unsigned_t< I > u = 0;
    for (;;)  {
        char c = *cursor;
        if ((c < '0') || ('9' < c)) {
            break;
        }
        ++cursor;
        u = (u * 10) + (c - '0');
    }
    i = I(u);
    if (sign == '-') {
        i = -i;
    }
}

template< typename F >
void read_float(F & result)
{
    static_assert(std::is_floating_point< F >::value, "!");
    char c = *cursor;
    std::uint8_t significand[std::numeric_limits< F >::digits10];
    auto s = significand;
    std::int32_t after = 0;
    std::int32_t before = 0;
    char sign = c;
    switch (c) {
    case '-' :
    case '+' :
        c = *++cursor;
    }
    [&]
    {
        bool d = false;
        for (;;) {
            switch (c) {
            case '.' :
                before = 1;
                break;
            case '0' ... '9' : {
                if (c != '0') {
                    d = true;
                }
                if (0 < before) {
                    ++before;
                }
                if (d) {
                    *s++ = (c - '0');
                    if (s == significand + sizeof significand) {
                        std::int32_t a = 0;
                        for (;;) {
                            switch ((c = *++cursor)) {
                            case '0' ... '9' :
                                ++a;
                                break;
                            case '.' :
                                after = a;
                                break;
                            default :
                                if ((before == 0) && (after == 0)) {
                                    after = a;
                                }
                                return;
                            }
                        }
                    }
                }
                break;
            }
            default :
                if (!d) {
                    *s++ = 0;
                }
                return;
            }
            c = *++cursor;
        }
    }();
    if (0 < before) {
        after -= (before - 1);
    }
    std::uint32_t exponent = 0;
    switch (c) {
    case 'e' :
    case 'E' : {
        c = *++cursor;
        char esign = c;
        switch (c) {
        case '-' :
        case '+' :
            c = *++cursor;
            break;
        }
        [&]
        {
            for (;;) {
                switch (c) {
                case '0' ... '9' :
                    exponent = (exponent * 10) + (c - '0');
                    break;
                default : {
                    return;
                }
                }
                c = *++cursor;
            }
        }();
        if (esign == '-') {
            after -= exponent;
        } else {
            after += exponent;
        }
    }
    }

    alignas(32) std::uint8_t bcd[10] = {};
    std::uint32_t b = 0;
    do {
        --s;
        if ((b % 2) == 0) {
            bcd[b / 2] = *s;
        } else {
            bcd[b / 2] |= (*s << 4);
        }
        ++b;
    } while (s != significand);

    if (sign == '-') {
        bcd[9] = (1 << 7);
    }

    asm(
    "fldl2t;"
    "fildl %[exp10];"
    "fmulp;"
    "fld %%st;"
    "frndint;"
    "fxch;"
    "fsub %%st(1), %%st;"
    "f2xm1;"
    "fld1;"
    "faddp;"
    "fscale;"
    "fstp %%st(1);"
    "fbld %[tbyte];"
    "fmulp;"
    : "=t"(result)
    : [exp10]"m"(after), [tbyte]"m"(bcd)
    : "st(1)", "st(2)"
    );
}

template< typename I >
void print_int(I value)
{
    if (value == 0) {
        uputchar('0');
        return;
    }
    std::make_unsigned_t< I > v;
    if (value < 0) {
        uputchar('-');
        v = decltype(v)(-value);
    } else {
        v = decltype(v)(value);
    }
    I rev = v;
    I count = 0;
    while ((rev % 10) == 0) {
        ++count;
        rev /= 10;
    }
    rev = 0;
    while (v != 0) {
        rev = (rev * 10) + (v % 10);
        v /= 10;
    }
    while (rev != 0) {
        uputchar("0123456789"[rev % 10]);
        rev /= 10;
    }
    while (0 != count) {
        --count;
        uputchar('0');
    }
}

}