Submission #559328

#	Time	Username	Problem	Language	Result	Execution time	Memory
559328		ahmet34	Handcrafted Gift (IOI20_gift)	C++14	0 / 100	617 ms	44472 KiB

gift

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

using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const int INF = 2e9, N = 1e6+10, M = 1e9+7, LOG = 16;
const ll LINF = 1e18;

struct SegTree {
    struct Node {
        int sum, lzy;
        Node(int sum = 0, int lzy = -1) : sum(sum), lzy(lzy) {}
    };
    vector<Node> t;
    vector<int> lo, hi;

    void init(int n) { 
        t.resize(n << 2); lo.resize(n << 2); hi.resize(n << 2); 
        build(1, 1, n);
    }

    void build(int k, int l, int r) {
        lo[k] = l;  hi[k] = r;
        int m = (l + r) / 2;
        if(l != m)
            build(k << 1, l, m),
            build(k << 1 | 1, m+1, r);    
    }

    void push(int k) {
        if(t[k].lzy != -1) {
            t[k].sum = hi[k] - lo[k] + 1;
            if(lo[k] != hi[k])
                t[k << 1].lzy = t[k << 1 | 1].lzy = t[k].lzy;
        }
        t[k].lzy = -1;
    }

    int qry(int x) { return qry(x, x); }
    int qry(int l, int r, int k = 1) {
        push(k);
        if(l <= lo[k] && hi[k] <= r) return t[k].sum;
        if(l > hi[k] || r < lo[k]) return 0;
        return qry(l, r, k << 1) + qry(l, r, k << 1 | 1);
    }

    void upd(int l, int r, int k = 1) {
        push(k);
        if(l > hi[k] || r < lo[k]) return;
        if(l <= lo[k] && hi[k] <= r) {
            t[k].lzy = 1; push(k);
            return;
        }
        upd(l, r, k << 1);
        upd(l, r, k << 1 | 1);
    }
};

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    SegTree seg;
    seg.init(n);

    for(int i = 0; i < r; ++i) a[i]++, b[i]++;

    for (int i = 0; i < r; i++) {
        if(x[i] == 1) {
            if(a[i] < b[i])
                seg.upd(a[i]+1, b[i]);
        }
    }
    for (int i = 0; i < r; i++) {
        if(x[i] == 2) {
            if(a[i] < b[i])
                if(seg.qry(a[i]+1, b[i]) == b[i] - a[i]) 
                    return 0;
        }
    }
    string s = "R";
    for(int i = 1; i < n; ++i) {
        if(seg.qry(i)) 
            s.push_back(s.back());
        else 
            s.push_back(s.back() == 'B' ? 'R' : 'B');
    }
    craft(s);
    return 1;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30