oj.uz

Submission #593593

# Submission time Handle Problem Language Result Execution time Memory
593593 2022-07-11T12:20:02 Z vovik Intercastellar (JOI22_ho_t1) C++17
25 / 100
 19 ms 5896 KB 
#include <bits/stdc++.h>

namespace IO {
    const int DPAIRSIZ = 1 << 10;
    char BB[DPAIRSIZ], *SS = BB, *TT = BB;

    inline char getcha() {
        return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT) ? EOF : *SS++;
    }

    template<typename T = int>
    inline T read() {
        T x = 0;
        int fu = 1;
        char c = getcha();
        while (c > 57 || c < 48) {
            if (c == 45) fu = -1;
            c = getcha();
        }
        while (c <= 57 && c >= 48) {
            x = x * 10 + c - 48;
            c = getcha();
        }
        x *= fu;
        return x;
    }

    template<typename T>
    inline void read(T &x) {
        x = 0;
        int fu = 1;
        char c = getcha();
        while (c > 57 || c < 48) {
            if (c == 45) fu = -1;
            c = getcha();
        }
        while (c <= 57 && c >= 48) {
            x = x * 10 + c - 48;
            c = getcha();
        }
        x *= fu;
    }

    template<typename T>
    inline void read(T *bg, T *ed) { while (bg != ed) read(*bg++); }

    inline void read(char &ch) {
        ch = getcha();
        while (ch <= 32) ch = getcha();
    }

    inline void read(char *s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void read(std::string &s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) s.push_back(ch), ch = getcha();
    }

    inline void sread(char *s) {
        char ch = getcha();
        while (ch < 32) ch = getcha();
        while (ch >= 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void pread(char *&s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void spread(char *&s) {
        char ch = getcha();
        while (ch < 32) ch = getcha();
        while (ch >= 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    template<typename T, typename ...Args>
    inline void read(T &x, Args &...args) {
        read(x);
        read(args...);
    }

    char out[DPAIRSIZ], *Out = out;
#define flush() fwrite(out, 1, Out - out, stdout)

    inline void putcha(char x) {
        *Out++ = x;
        if (Out - out >= (DPAIRSIZ)) flush(), Out = out;
    }

    template<typename T>
    inline void fprint(T x) {
        if (x < 0) putcha(45), x = -x;
        if (x > 9) fprint(x / 10);
        putcha(x % 10 + 48);
    }

    inline void print() { putcha(10); }

    template<typename T>
    inline void print(T x) {
        fprint(x);
        putcha(10);
    }

    inline void print(char *ch) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
    }

    inline void put(char *ch) { while (*ch != '\0') putcha(*(ch++)); }

    inline void print(const char *ch) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
    }

    inline void put(const char *ch) { while (*ch != '\0') putcha(*(ch++)); }

    template<typename T, typename ...Args>
    inline void print(T x, Args ...args) {
        fprint(x);
        putcha(32);
        print(args...);
    }

    template<typename ...Args>
    inline void print(const char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(32);
        print(args...);
    }

    template<typename ...Args>
    inline void print(char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(32);
        print(args...);
    }

    template<typename T, typename ...Args>
    inline void printl(T x, Args ...args) {
        fprint(x);
        putcha(10);
        printl(args...);
    }

    template<typename ...Args>
    inline void printl(const char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
        printl(args...);
    }

    template<typename ...Args>
    inline void printl(char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
        printl(args...);
    }

    template<typename T>
    inline void sprint(T x) {
        fprint(x);
        putcha(32);
    }

    template<typename T, typename ...Args>
    inline void sprint(T x, Args ...args) {
        fprint(x);
        putcha(32);
        sprint(args...);
    }

    template<typename T>
    inline void sprint(T *bg, T *ed) { while (bg != ed) sprint(*bg++); }

    template<typename T>
    inline void print(T *bg, T *ed) {
        while (bg != ed) sprint(*bg++);
        putcha(10);
    }

    template<typename T>
    inline void printl(T *bg, T *ed) { while (bg != ed) print(*bg++); }

    class AutoFlush {
    public:
        ~AutoFlush() { flush(); }
    } __AutoFlush;
} // namespace IO
using namespace IO;

#define vc vector

#define nd node*
#define pnd pair<nd, nd>

using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

#define int ll

int32_t main() {
    int n;
    read(n);
    vc<pair<int, int>> a;
    for (int i = 0; i < n; ++i) {
        int x = read();
        a.emplace_back(1, 0);
        while (!(x & 1)) x /= 2, a.back().first *= 2;
        a.back().second = x;
    }
    vc<ll> pref(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + a[i].first;;
    }
    pref.erase(pref.begin());
    int q;
    read(q);
    while (q--) {
        ll x = read();
        print(a[lower_bound(pref.begin(), pref.end(), x) - pref.begin()].second);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 14 ms 5096 KB Output is correct
4 Correct 9 ms 1996 KB Output is correct
5 Correct 18 ms 5896 KB Output is correct
6 Correct 12 ms 4676 KB Output is correct
7 Correct 19 ms 5808 KB Output is correct
8 Correct 16 ms 5888 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 14 ms 5096 KB Output is correct
4 Correct 9 ms 1996 KB Output is correct
5 Correct 18 ms 5896 KB Output is correct
6 Correct 12 ms 4676 KB Output is correct
7 Correct 19 ms 5808 KB Output is correct
8 Correct 16 ms 5888 KB Output is correct
9 Correct 0 ms 304 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Halted 0 ms 0 KB -