Submission #1046093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046093	2024-08-06T09:59:17 Z	dilanyan	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	1306 ms	2392 KB

Main

//-------------dilanyan------------\\ 
 
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
 
//------------------Kargpefines--------------------\\ 
 
#define ll long long
#define pb push_back
#define all(u) (u).begin(), (u).end()
#define pqueue priority_queue
#define upper upper_bound
#define lower lower_bound
#define umap unordered_map
#define uset unordered_set
 
void KarginSet(string name = "") {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
 
//-------------------KarginConstants------------------\\ 
 
const ll mod = 1e9 + 7;
const ll inf = 2e9;
 
//-------------------KarginCode-----------------------\\ 
 
const int N = 100005, M = 1000005;

int n, m;

int s[N], f[N];

int tree[4 * N], add[4 * N];

struct segtree {

    int size = 1;

    void init() {
        while (size < m) size <<= 1;
    }

    void push(int x, int lx, int rx) {
        if (rx - lx == 1) return;
        if (tree[x] == 0) {
            tree[2 * x + 1] = tree[2 * x + 2] = 0;
        }
        else if (tree[x] == min(m, rx) - min(lx, m)) {
            int mid = (lx + rx) / 2;
            tree[2 * x + 1] = min(mid, m) - min(lx, m);
            tree[2 * x + 2] = min(rx, m) - min(mid, m);
        }
    }

    void set(int l, int r, int v, int x, int lx, int rx) {
        push(x, lx, rx);
        if (lx >= r || rx <= l) return;
        if (lx >= l && rx <= r) {
            tree[x] = v * (rx - lx);
            return;
        }
        int mid = (lx + rx) / 2;
        set(l, r, v, 2 * x + 1, lx, mid);
        set(l, r, v, 2 * x + 2, mid, rx);
        tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }

    void set(int l, int r, int v) {
        set(l, r,v , 0, 0, size);
    }

    int get(int l, int r, int x, int lx, int rx) {
        push(x, lx, rx);
        if (lx >= r || rx <= l) return 0;
        if (lx >= l && rx <= r) return tree[x];
        int mid = (lx + rx) / 2;
        int getl = get(l, r, 2 * x + 1, lx, mid),
            getr = get(l, r, 2 * x + 2, mid, rx);
        return getl + getr;
    }

    int get(int l, int r) {
        return get(l, r, 0, 0, size);
    }

};

void KarginSolve() {
    cin >> n >> m;
    for (int i = 0;i < n;i++) cin >> s[i];
    for (int i = 0;i < m;i++) cin >> f[i];
    ll l = 0, r = 1e9, ans = -1;
    assert(n != 1);
    segtree st;
    st.init();
    while (l <= r) {
        ll mid = (l + r) / 2;
        st.set(0, m, 0);
        assert(tree[0] == 0);
        for (int i = 0;i < n;i++) {
            int sp = lower(f, f + m, s[i] - mid) - f;
            int ep = upper(f, f + m, s[i]) - f;
            if (st.get(sp, ep) != ep - sp && f[sp] != s[i]) {
                st.set(sp, ep, 1);
            }
            else {
                sp = lower(f, f + m, s[i]) - f;
                ep = upper(f, f + m, s[i] + mid) - f;
                st.set(sp, ep, 1);
            }
        }
        if (tree[0] == m) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    if (ans == -1) cout << -1 << '\n';
    else {
        cout << ans << '\n';
        st.set(0, m, 0);
        for (int i = 0;i < n;i++) {
            int sp = lower(f, f + m, s[i] - ans) - f;
            int ep = upper(f, f + m, s[i]) - f;
            if (st.get(sp, ep) != ep - sp && f[sp] != s[i]) {
                st.set(sp, ep, 1);
                cout << 'L';
            }
            else {
                sp = lower(f, f + m, s[i]) - f;
                ep = upper(f, f + m, s[i] + ans) - f;
                st.set(sp, ep, 1);
                cout << 'R';
            }
        }
        cout << '\n';
    }
}

int main() {
    KarginSet();
    int test = 1;
    //cin >> test;
    while (test--) {
        KarginSolve();
    }
    return 0;
}

Compilation message

Main.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //-------------dilanyan------------\\
      | ^
Main.cpp:8:1: warning: multi-line comment [-Wcomment]
    8 | //------------------Kargpefines--------------------\\
      | ^
Main.cpp:27:1: warning: multi-line comment [-Wcomment]
   27 | //-------------------KarginConstants------------------\\
      | ^
Main.cpp:32:1: warning: multi-line comment [-Wcomment]
   32 | //-------------------KarginCode-----------------------\\
      | ^
Main.cpp: In function 'void KarginSet(std::string)':
Main.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Correct
2	Runtime error	1 ms	604 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #1
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	604 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Correct
2	Correct	22 ms	1672 KB	Correct
3	Correct	86 ms	572 KB	Correct
4	Correct	1252 ms	2128 KB	Correct
5	Correct	1238 ms	2028 KB	Correct
6	Correct	0 ms	2392 KB	Correct
7	Correct	0 ms	348 KB	Correct
8	Correct	1252 ms	1876 KB	Correct
9	Correct	1306 ms	1876 KB	Correct
10	Correct	1256 ms	1868 KB	Correct
11	Correct	305 ms	860 KB	Correct
12	Correct	509 ms	1624 KB	Correct
13	Correct	1243 ms	1560 KB	Correct
14	Correct	1187 ms	1648 KB	Correct
15	Correct	1154 ms	1512 KB	Correct
16	Correct	1208 ms	1588 KB	Correct