oj.uz

Submission #1045319

# Submission time Handle Problem Language Result Execution time Memory
1045319 2024-08-05T20:23:37 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 100424 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
#pragma GCC target("popcnt,abm,mmx,avx,avx2,lzcnt,bmi,bmi2,fma,sse,sse2,sse3,sse4,sse4.1,sse4.2,tune=native")
#pragma GCC optimize("-fipa-sra,-fgcse-lm,-fgcse,inline,unroll-all-loops,no-stack-protector,O3,fast-math,Ofast")
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;
    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;
    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:20:13: warning: 'Node::R' will be initialized after [-Wreorder]
   20 |   Node *L, *R;
      |             ^
street_lamps.cpp:19:10: warning:   'int Node::val' [-Wreorder]
   19 |   int Y, val;
      |          ^~~
street_lamps.cpp:22:3: warning:   when initialized here [-Wreorder]
   22 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp:19:10: warning: 'Node::val' will be initialized after [-Wreorder]
   19 |   int Y, val;
      |          ^~~
street_lamps.cpp:18:10: warning:   'int Node::sum' [-Wreorder]
   18 |   int X, sum = 0, sum2 = 0;
      |          ^~~
street_lamps.cpp:22:3: warning:   when initialized here [-Wreorder]
   22 |   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:114:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:133:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |   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:165:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  165 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:240: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]
  240 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:266:15: warning: unused variable 'aa' [-Wunused-variable]
  266 |   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 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 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 1018 ms 41268 KB Output is correct
2 Correct 1298 ms 40120 KB Output is correct
3 Correct 1856 ms 40116 KB Output is correct
4 Correct 3423 ms 80148 KB Output is correct
5 Correct 2146 ms 67796 KB Output is correct
6 Correct 3917 ms 84952 KB Output is correct
7 Correct 1847 ms 76492 KB Output is correct
8 Correct 155 ms 57316 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11096 KB Output is correct
2 Correct 4 ms 11100 KB Output is correct
3 Correct 4 ms 11048 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Execution timed out 5097 ms 100424 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 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 5 ms 11100 KB Output is correct
4 Correct 7 ms 11100 KB Output is correct
5 Correct 1020 ms 62176 KB Output is correct
6 Correct 2347 ms 72648 KB Output is correct
7 Correct 4030 ms 84004 KB Output is correct
8 Execution timed out 5072 ms 100032 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 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1018 ms 41268 KB Output is correct
9 Correct 1298 ms 40120 KB Output is correct
10 Correct 1856 ms 40116 KB Output is correct
11 Correct 3423 ms 80148 KB Output is correct
12 Correct 2146 ms 67796 KB Output is correct
13 Correct 3917 ms 84952 KB Output is correct
14 Correct 1847 ms 76492 KB Output is correct
15 Correct 155 ms 57316 KB Output is correct
16 Correct 6 ms 11096 KB Output is correct
17 Correct 4 ms 11100 KB Output is correct
18 Correct 4 ms 11048 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Execution timed out 5097 ms 100424 KB Time limit exceeded
21 Halted 0 ms 0 KB -