oj.uz

Submission #962895

# Submission time Handle Problem Language Result Execution time Memory
962895 2024-04-14T09:28:00 Z hariaakas646 Election (BOI18_election) C++14
100 / 100
 431 ms 36436 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;


void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

struct Data {
    int tot = 0;
    int mi = 0;
    int mil = 0;
    int mir = 0;
};

template <class T>
struct SegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
    }

    T operation(T x, T y)
    {
        T out;
        out.tot = x.tot + y.tot;
        out.mil = x.mil;
        out.mil = min(out.mil, x.tot+y.mil);
        out.mir = y.mir;
        out.mir = min(out.mir, x.mir + y.tot);
        // out.mi = min(x.mi, y.mi);
        // out.mi = min(out.mi, x.mir + y.mil);
        out.mi = min(min(x.mi+y.tot, y.mi+x.tot), x.mil + y.mir);
        return out;
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    void update(int x, int l, int r, int id, T val)
    {
        if (l == r)
        {
            segtree[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (id <= mid)
        {
            update(2 * x + 1, l, mid, id, val);
        }
        else
        {
            update(2 * x + 2, mid + 1, r, id, val);
        }
        recalculate(x);
    }

    void update(int id, T val)
    {
        update(0, 0, size - 1, id, val);
    }

    T query(int x, int l, int r, int lx, int rx)
    {
        if (lx > r || rx < l)
        {
            return def;
        }
        if (lx <= l && r <= rx)
        {
            return segtree[x];
        }
        int mid = (l + r) / 2;
        T v1 = query(2 * x + 1, l, mid, lx, rx);
        T v2 = query(2 * x + 2, mid + 1, r, lx, rx);
        return operation(v1, v2);
    }

    T query(int lx, int rx)
    {
        return query(0, 0, size - 1, lx, rx);
    }
};

int main() {
    // usaco();
    int n;
    scd(n);
    string str;
    cin >> str;

    SegTree<Data> segtree;
    Data tmp;
    segtree.init(n, tmp);

    frange(i, n) {

        if(str[i] == 'C') {
            tmp.tot = 1;
            tmp.mi = tmp.mil = tmp.mir = 0;
            segtree.set(i, tmp);
        }
        else {
            tmp.tot = tmp.mi = tmp.mil = tmp.mir = -1;
            segtree.set(i, tmp);
        }
    }
    segtree.build();

    int q;scd(q);

    frange(_, q) {
        int l, r;
        scd(l);
        scd(r);
        l--;
        r--;
        printf("%d\n", -segtree.query(l, r).mi);
    }
}

Compilation message

election.cpp: In function 'void usaco()':
election.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:153:5: note: in expansion of macro 'scd'
  153 |     scd(n);
      |     ^~~
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:175:11: note: in expansion of macro 'scd'
  175 |     int q;scd(q);
      |           ^~~
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:179:9: note: in expansion of macro 'scd'
  179 |         scd(l);
      |         ^~~
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:180:9: note: in expansion of macro 'scd'
  180 |         scd(r);
      |         ^~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 452 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 2 ms 344 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 452 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 54 ms 7960 KB Output is correct
7 Correct 43 ms 7912 KB Output is correct
8 Correct 43 ms 7892 KB Output is correct
9 Correct 39 ms 7772 KB Output is correct
10 Correct 46 ms 7764 KB Output is correct
11 Correct 44 ms 8020 KB Output is correct
12 Correct 44 ms 8020 KB Output is correct
13 Correct 45 ms 7912 KB Output is correct
14 Correct 44 ms 8016 KB Output is correct
15 Correct 47 ms 7864 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 452 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 54 ms 7960 KB Output is correct
7 Correct 43 ms 7912 KB Output is correct
8 Correct 43 ms 7892 KB Output is correct
9 Correct 39 ms 7772 KB Output is correct
10 Correct 46 ms 7764 KB Output is correct
11 Correct 44 ms 8020 KB Output is correct
12 Correct 44 ms 8020 KB Output is correct
13 Correct 45 ms 7912 KB Output is correct
14 Correct 44 ms 8016 KB Output is correct
15 Correct 47 ms 7864 KB Output is correct
16 Correct 431 ms 35324 KB Output is correct
17 Correct 370 ms 34708 KB Output is correct
18 Correct 421 ms 35200 KB Output is correct
19 Correct 348 ms 34564 KB Output is correct
20 Correct 421 ms 34364 KB Output is correct
21 Correct 428 ms 36436 KB Output is correct
22 Correct 413 ms 36104 KB Output is correct
23 Correct 379 ms 36128 KB Output is correct
24 Correct 427 ms 35920 KB Output is correct
25 Correct 388 ms 35312 KB Output is correct