oj.uz

Submission #1103552

# Submission time Handle Problem Language Result Execution time Memory
1103552 2024-10-21T08:50:53 Z LTTrungCHL Election (BOI18_election) C++17
100 / 100
 791 ms 49368 KB 
///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
vector <int> lg2;
//void MAKE_LOG_ARR(int n){
//    lg2.resize(n + 3);
//    for (int i = 1;i <= n;++i){
//        lg2[i] = __lg(i);
//    }
//}
const long long oo = 1e9+7;
const int N = 5 * 1e5 + 10;
int n, q;
string s;
int a[N];
int tree[N * 4], lazy[N * 4];
vector <pair <int, int>> query[N];
vector <int> del;
int ans[N];
void down(int id, int l, int r){
    if (l != r){
        tree[id * 2] += lazy[id];
        tree[id * 2 + 1] += lazy[id];
        lazy[id * 2] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];
    }
    lazy[id] = 0;
    return;
}
void update(int id, int l, int r, int u, int v, int val){
    if (lazy[id] != 0){
        down(id, l, r);
    }
    if (l > v or r < u) return;
    if (l >= u and r <= v){
        tree[id] += val;
        lazy[id] += val;
        return;
    }
    int mid = (l + r)/2;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
    tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
    return;
}
int get(int id, int l, int r, int u, int v){
    if (u > n) return 0;
    if (lazy[id] != 0){
        down(id, l, r);
    }
    if (l > v or r < u) return oo;
    if (l >= u and r <= v){
        return tree[id];
    }
    int mid = (l + r)/2;
    return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
void solve(){
    cin >> n;
    cin >> s;
    for (int i = 0;i < s.size();++i){
        if (s[i] == 'C'){
            a[i + 1] = 1;
        }  else a[i + 1] = -1;
    }
    for (int i = 1;i <= n;++i){
        update(1,1,n,1,i,a[i]);
    }
    cin >> q;
    for (int i = 1;i <= q;++i){
        int l, r;
        cin >> l >> r;
        query[l].pb({r, i});
    }
    for (int i = n;i >= 1;--i){
        if (a[i] == 1){
            if (!del.empty()){
                int zz = del.back();
                update(1,1,n,1,zz,-1);
                del.pop_back();
            }
        } else {
            update(1,1,n,1,i,1);
            del.pb(i);
        }
        for (int j = 0;j < query[i].size();++j){
            int id = query[i][j].S;
            int r = query[i][j].F;
            int res = del.size();
            int ll = 0, rr = del.size() - 1;
            while (ll <= rr){
                int mid = (ll + rr)/2;
                if (del[mid] <= r){
                    rr = mid - 1;
                    res = mid;
                } else ll = mid + 1;
            }
            int sz = del.size() - 1;
//            cout << id <<" : ";
//            for (int z = 1;z <= n;++z){
//                cout << get(1,1,n,z,z) <<" ";
//            }
//            cout <<"\n";
//            cout << id <<" "<<(sz - res + 1) <<" "<<get(1,1,n,i,r) <<" "<< get(1,1,n,r + 1,r + 1) <<"\n";
            ans[id] = (sz - res + 1) + abs(min(0,get(1,1,n,i,r) - get(1,1,n,r + 1,r + 1)));
        }
    }
    for (int i = 1;i <= q;++i){
        cout << ans[i] <<"\n";
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("ltt.inp", "r")){
        freopen("ltt.inp", "r", stdin);
        freopen("ltt.out", "w", stdout);
    }
//    int t;
//    cin >> t;
//    while(t--){
    solve();
//    }
    return 0;
}

Compilation message

election.cpp: In function 'void solve()':
election.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0;i < s.size();++i){
      |                    ~~^~~~~~~~~~
election.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j = 0;j < query[i].size();++j){
      |                        ~~^~~~~~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen("ltt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
election.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen("ltt.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18768 KB Output is correct
2 Correct 5 ms 18936 KB Output is correct
3 Correct 5 ms 18768 KB Output is correct
4 Correct 6 ms 19024 KB Output is correct
5 Correct 6 ms 18768 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18768 KB Output is correct
2 Correct 5 ms 18936 KB Output is correct
3 Correct 5 ms 18768 KB Output is correct
4 Correct 6 ms 19024 KB Output is correct
5 Correct 6 ms 18768 KB Output is correct
6 Correct 89 ms 22004 KB Output is correct
7 Correct 68 ms 21324 KB Output is correct
8 Correct 72 ms 21620 KB Output is correct
9 Correct 72 ms 21836 KB Output is correct
10 Correct 105 ms 21836 KB Output is correct
11 Correct 85 ms 22032 KB Output is correct
12 Correct 103 ms 22092 KB Output is correct
13 Correct 83 ms 22348 KB Output is correct
14 Correct 84 ms 21988 KB Output is correct
15 Correct 81 ms 21840 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18768 KB Output is correct
2 Correct 5 ms 18936 KB Output is correct
3 Correct 5 ms 18768 KB Output is correct
4 Correct 6 ms 19024 KB Output is correct
5 Correct 6 ms 18768 KB Output is correct
6 Correct 89 ms 22004 KB Output is correct
7 Correct 68 ms 21324 KB Output is correct
8 Correct 72 ms 21620 KB Output is correct
9 Correct 72 ms 21836 KB Output is correct
10 Correct 105 ms 21836 KB Output is correct
11 Correct 85 ms 22032 KB Output is correct
12 Correct 103 ms 22092 KB Output is correct
13 Correct 83 ms 22348 KB Output is correct
14 Correct 84 ms 21988 KB Output is correct
15 Correct 81 ms 21840 KB Output is correct
16 Correct 791 ms 47564 KB Output is correct
17 Correct 550 ms 43488 KB Output is correct
18 Correct 643 ms 44480 KB Output is correct
19 Correct 600 ms 46048 KB Output is correct
20 Correct 655 ms 46560 KB Output is correct
21 Correct 727 ms 48924 KB Output is correct
22 Correct 688 ms 48352 KB Output is correct
23 Correct 710 ms 49368 KB Output is correct
24 Correct 708 ms 48552 KB Output is correct
25 Correct 730 ms 47840 KB Output is correct