oj.uz

Submission #932671

# Submission time Handle Problem Language Result Execution time Memory
932671 2024-02-24T02:42:39 Z VinhLuu Street Lamps (APIO19_street_lamps) C++17
40 / 100
 135 ms 38212 KB 
// REPUTATION RATING =

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 3e5 + 5;
//const int oo = 1e9;
const int mod = 1e9 + 7;

int n, q, a[N], L[N], R[N], X[N];
string s, T[N];

namespace sub1{
    int m[105][105];
    void solve(){
        for(int i = 1; i <= n; i ++) m[1][i] = a[i];
        for(int t = 1; t <= q; t ++){
            string type; cin >> type;
            if(type[0] == 't'){
                int x; cin >> x;
                a[x] = 1 - a[x];
            }else{
                int l, r, ans = 0; cin >> l >> r;
                for(int j = 1; j <= t; j ++){
                    bool ff = true;
                    for(int i = l; i < r; i ++) if(m[j][i] == 0){
                        ff = false;
                        break;
                    }
                    ans += ff;
                }
                cout << ans << "\n";
            }
            for(int i = 1;i <= n; i ++) m[t + 1][i] = a[i];
        }
    }
}

namespace sub2{
    bool on[N];
    int cnt[N], f[N];
    void solve(){
        for(int i = 1; i <= n; i ++){
            if(a[i] == 1){
                f[i] = 1;
                on[i] = true;
            }else{
                on[i] = false;
                f[i] = -1;
            }
        }
        for(int t = 1; t <= q; t ++){
            string type = T[t];
            if(type[0] == 't'){
                int x = X[t];
                if(on[x]){
                    cnt[x] += t - f[t] + 1;
                }else{
                    f[x] = t + 1;
                }
                on[x] = 1 - on[x];
            }else{
                int l = L[t], r = R[t], ans = 0; cin >> l >> r;
                if(on[l]) cout << cnt[l] + t - f[l] + 1 << "\n";
                else cout << cnt[l] << "\n";
            }
        }
    }
}

namespace sub3{
    bool on[N];
    int cnt[N], f[N], st[N << 1];
    int get(int l,int r){
        r++;
        int ret = 1;
        for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
            if(l & 1) ret = max(ret, st[l ++]);
            if(r & 1) ret = max(ret, st[-- r]);
        }
        return ret;
    }
    void solve(){
        for(int i = 1; i <= n; i ++){
            if(a[i] == 1){
                f[i] = 1;
                on[i] = true;
            }else{
                on[i] = false;
                f[i] = 1e9;
            }
        }
        for(int t = 1; t <= q; t ++){
            string type = T[t];
            if(type[0] == 't'){
                int x = X[t]; //cin >> x;
                f[x] = t + 1;
            }
        }
        for(int i = 1; i <= n; i ++) st[i + n - 1] = f[i];
        for(int i = n - 1; i >= 1; i --) st[i] = max(st[i << 1], st[i << 1|1]);
        for(int t = 1; t <= q; t ++){
            string type = T[t];
            if(type[0] == 't') continue;

            int l = L[t], r = R[t], ans = 0; cin >> l >> r;
            int u = get(l, r - 1);
            if(u > t) cout << 0 << "\n";
            else cout << t - u + 1 << "\n";
        }
    }
}


#define LOCAL

#ifdef LOCAL
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> q >> s;
    for(int i = 1; i <= n; i ++) a[i] = s[i - 1] - '0';
    if(n <= 100 && q <= 100)
        sub1 :: solve();
    else{
        bool gg = true;
        for(int i = 1; i <= q; i ++) {
            cin >> T[i];
            if(T[i][0] == 't') cin >> X[i];
            else{
                cin >> L[i] >> R[i];
                if(R[i] - L[i] > 1) gg = false;
            }
        }
        if(gg) sub2 :: solve();
        else
            sub3 :: solve();
    }
}
#endif // LOCAL

Compilation message

street_lamps.cpp: In function 'void sub2::solve()':
street_lamps.cpp:70:41: warning: unused variable 'ans' [-Wunused-variable]
   70 |                 int l = L[t], r = R[t], ans = 0; cin >> l >> r;
      |                                         ^~~
street_lamps.cpp: In function 'void sub3::solve()':
street_lamps.cpp:113:37: warning: unused variable 'ans' [-Wunused-variable]
  113 |             int l = L[t], r = R[t], ans = 0; cin >> l >> r;
      |                                     ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 3 ms 12784 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 27472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct
2 Correct 4 ms 21076 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 50 ms 34424 KB Output is correct
6 Correct 75 ms 35240 KB Output is correct
7 Correct 101 ms 35812 KB Output is correct
8 Correct 135 ms 38212 KB Output is correct
9 Correct 69 ms 26656 KB Output is correct
10 Correct 75 ms 26964 KB Output is correct
11 Correct 77 ms 27100 KB Output is correct
12 Correct 130 ms 36632 KB Output is correct
13 Correct 131 ms 38044 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Incorrect 4 ms 20828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 3 ms 12784 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 61 ms 27472 KB Output isn't correct
9 Halted 0 ms 0 KB -