oj.uz

Submission #1045202

# Submission time Handle Problem Language Result Execution time Memory
1045202 2024-08-05T18:51:32 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 104644 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 2e6+100, M = 3e5+10, K = 52, MX = 30;


struct Node{
  int X, sum = 0, sum2 = 0;
  int Y, val;
  Node *L, *R;
  Node(){}
  Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
};
typedef Node* Nodep; 
 
void upd_sz(Nodep v){
  if(v){
    v->sum = v->val * v->X;
    v->sum2 = v->val;
    if(v->L) v->sum += v->L->sum;
    if(v->R) v->sum += v->R->sum;

    if(v->L) v->sum2 += v->L->sum2;
    if(v->R) v->sum2 += v->R->sum2;
  }
}

 
pair<Nodep, Nodep> split(Nodep v, int key){
  if(!v){
    return {v, v};
  }
  else if(v->X <= key){
    auto p = split(v->R, key);
    v->R = p.first;
    upd_sz(v);
    return {v, p.second};
  }else{
    auto p = split(v->L, key);
    v->L = p.second;
    upd_sz(v);
    return {p.first, v};
  }
}
 
Nodep merge(Nodep l, Nodep r){
  if(!l || !r){
    return l ? l : r;
  }else if(l->Y > r->Y){
    auto p = merge(l->R, r);
    l->R = p;
    upd_sz(l);
    return l;
  }else{
    auto p = merge(l, r->L);
    r->L = p;
    upd_sz(r);
    return r;
  }
}
Nodep insert(Nodep v, Nodep it){
  if(!v) return it;
  if(v->Y > it->Y){
    if(v->X <= it->X) v->R = insert(v->R, it);
    else v->L = insert(v->L, it);
    upd_sz(v);
    return v;
  }else{
    auto a = split(v, it->X);
    it->L = a.ff;
    it->R = a.ss;
    upd_sz(it);
  }
  return it;
}

void dfs(Nodep t){
  if(t->L) dfs(t->L);
  if(t->R) dfs(t->R);
  free(t);
}
  
void dfs2(Nodep t){
  // if(t->L)
  // cout << "go left: ";
  if(t->L) dfs2(t->L);
  // cout << "par: ";
  // cout << t->Y << ' ';
  // if(t->R)
  // cout << "go right: ";
  if(t->R) dfs2(t->R);
}
 

int n, q, ans[M];
string s;
Nodep T[N];

void build(int l, int r, int k){
  if(l == r){
    T[k] = new Node(0, 0);
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k] = new Node(0, 0);
}

void upd(int l, int r, int p, int k, int t1, int t2){
  if(!(l == 1 && r == n + 1)){
    Nodep A = new Node(t1, 1);
    Nodep B = new Node(t2, -1);
    T[k] = insert(T[k], A);
    T[k] = insert(T[k], B);
  }
  // dfs2(T[k]);en;en;
   // cout << "insert:" << l << ' ' << r << ' ' << p << ' ' << t1 << ' ' << t2 << '\n';

  if(l == r){
    return;
  }
  int m = l+r>>1;
  if(p <= m) upd(l, m, p, k<<1, t1, t2);
  else upd(m+1, r, p, k<<1|1, t1, t2);
}

int get(int l, int r, int p, int k, ll tm){
  if(l == r){
    int val = 0;
    auto halves = split(T[k], tm);
    val += halves.ff->sum2 * tm - halves.ff->sum;
        // cout  << halves.ff->X << ' ' << halves.ff->val << ' ' << tm << ' ' << l << ' ' << r << ' ' << halves.ff->sum2 << ' ' << halves.ff->sum << ' ' << val << '\n';

    T[k] = merge(halves.ff, halves.ss);

    return val;
  }
  // dfs2(T[k]);en;en;
  int m = l+r>>1;
  if(p <= m){
    int val = 0;
    auto halves = split(T[k<<1|1], tm);
    val += halves.ff->sum2 * tm - halves.ff->sum;
    // cout << halves.ff->X << ' ' << halves.ff->val << ' ' << tm << ' ' << l << ' ' << r << ' ' << halves.ff->sum2 << ' ' << halves.ff->sum << ' ' << val << '\n';

    T[k<<1|1] = merge(halves.ff, halves.ss);

    return get(l, m, p, k<<1, tm) + val;
  }
  return get(m+1, r, p, k<<1|1, tm);
}

void F(int l, int r, int p, int k){
  if(l == r){
    dfs(T[k]);
    return;
  }
  int m = l+r>>1;
  if(p <= m) F(l, m, p, k<<1);
  else F(m+1, r, p, k<<1|1);
  if(p == r) dfs(T[k]);
}

vector<array<int, 3>> Q[M];
void solve(){
  // cout << sizeof(Node) << '\n';
  cin >> n >> q >> s;

  vector<array<int, 4>> R;
  int last = 1;
  s += '0';
  set<array<int, 3>> S;
  for(int i = 0; i <= n; ++i){
    if(s[i] == '0'){
      S.insert({last, i + 1, 0});
      last = i + 2;
    }
  }

  int qq = 0;

  for(int i = 0; i < q; ++i){
    string x; int a, b; cin >> x;
    if(x == "toggle"){
      cin >> a;
      --a;
      if(s[a] == '0'){
        s[a] = '1';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        auto it2 = prev(it);
        auto x = *it, y = *it2;
        S.erase(it2);
        S.erase(S.find(x));
        S.insert({y[0], x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
        R.pb({y[0], y[1], y[2], i + 1});
      }else{
        s[a] = '0';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        it = prev(it);
        auto x = *it;
        S.erase(it);
        S.insert({x[0], a, i + 1}); // check
        S.insert({a + 1, x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
      }
    }else{
      cin >> a >> b;
      Q[a].pb({b, i + 1, qq});
      qq++;
    }
  }

  for(auto p: S){
    R.pb({p[0], p[1], p[2], q});
  }
  S.clear();

  sort(all(R));
  build(1, n + 1, 1);
  int p = 0;

  // for(auto f: R){
  //   cout << f[0] << ' ' << f[1] << ' ' << f[2] << ' ' << f[3] << '\n';
  // }
  // en;en;

  for(int l = 1; l <= n + 1; ++l){
    while(p < R.size() && R[p][0] == l){
            // cout << R[p][0] << ' ' << R[p][1] << ' ' << R[p][2] << ' ' << R[p][3] << '\n';

      int r = R[p][1], t1 = R[p][2], t2 = R[p][3];
      upd(1, n+1, r, 1, t1, t2);
      ++p;
    }
    for(auto query: Q[l]){
      int r = query[0], tm = query[1], idx = query[2];
            // cout << l << ' ' << r << '\n';

      ans[idx] = get(1, n + 1, r, 1, tm);
      //  cout << ans[idx] << ' ';
      // en;en;
    }
    F(1, n+1, l, 1);
  }



  for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

street_lamps.cpp: In constructor 'Node::Node(int, int)':
street_lamps.cpp:18:13: warning: 'Node::R' will be initialized after [-Wreorder]
   18 |   Node *L, *R;
      |             ^
street_lamps.cpp:17:10: warning:   'int Node::val' [-Wreorder]
   17 |   int Y, val;
      |          ^~~
street_lamps.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp:17:10: warning: 'Node::val' will be initialized after [-Wreorder]
   17 |   int Y, val;
      |          ^~~
street_lamps.cpp:16:10: warning:   'int Node::sum' [-Wreorder]
   16 |   int X, sum = 0, sum2 = 0;
      |          ^~~
street_lamps.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:112:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:131:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, long long int)':
street_lamps.cpp:148:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:167:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:242:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:268:15: warning: unused variable 'aa' [-Wunused-variable]
  268 |   int tt = 1, aa;
      |               ^~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1127 ms 42540 KB Output is correct
2 Correct 1306 ms 41396 KB Output is correct
3 Correct 1997 ms 41396 KB Output is correct
4 Correct 3443 ms 82756 KB Output is correct
5 Correct 2270 ms 67792 KB Output is correct
6 Correct 3855 ms 83656 KB Output is correct
7 Correct 1919 ms 80836 KB Output is correct
8 Correct 162 ms 63204 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Execution timed out 5080 ms 102768 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 4 ms 10840 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 6 ms 11100 KB Output is correct
5 Correct 1042 ms 65812 KB Output is correct
6 Correct 2469 ms 75768 KB Output is correct
7 Correct 4152 ms 86476 KB Output is correct
8 Execution timed out 5035 ms 104644 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1127 ms 42540 KB Output is correct
9 Correct 1306 ms 41396 KB Output is correct
10 Correct 1997 ms 41396 KB Output is correct
11 Correct 3443 ms 82756 KB Output is correct
12 Correct 2270 ms 67792 KB Output is correct
13 Correct 3855 ms 83656 KB Output is correct
14 Correct 1919 ms 80836 KB Output is correct
15 Correct 162 ms 63204 KB Output is correct
16 Correct 7 ms 11096 KB Output is correct
17 Correct 5 ms 11100 KB Output is correct
18 Correct 3 ms 10844 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Execution timed out 5080 ms 102768 KB Time limit exceeded
21 Halted 0 ms 0 KB -