oj.uz

Submission #1037195

# Submission time Handle Problem Language Result Execution time Memory
1037195 2024-07-28T10:24:12 Z modwwe Street Lamps (APIO19_street_lamps) C++17
40 / 100
 4471 ms 524288 KB 
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e9;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b,c,d,e,f;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l,s33;
int  i,s10,s12;
int kk;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
//     fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    //  modwwe
    phongbeo();
}
string s;
  struct BIT2D{
      ///https://hackmd.io/@socpite/rkM_5OWIn
      vector<int>bit[300002];
      vector<int> bit2[300002];
   void fake_up(int x,int y,int z)
    {
       for(x;x<=n;x+=x&-x)
                for(int y2=y;y2<=n;y2+=y2&-y2)
                bit[x].pb(y2);
    }

       void fake_get(int x,int y)
         { int ss=0;
              for(x;x;x-=x&-x)
                for(int y2=y;y2;y2-=y2&-y2)
                  bit[x].pb(y2);
         }
         void fake_upd(int x, int y, int u, int v, int val) {
    fake_up(x, y, val);
    fake_up(x, v + 1, -val);
    fake_up(u + 1, y, -val);
    fake_up(u + 1, v + 1, val);
}
void setup()
{
     for(int i=1;i<=n;i++){
 if(bit[i].size()!=0){
            bit[i].push_back(0);
      sort(bit[i].begin(),bit[i].end());
        bit[i].erase(unique(bit[i].begin(), bit[i].end()), bit[i].end());
 bit2[i].assign(bit[i].size(),0);}
     }

}
void up(int x,int y,int z)
    {
       for(x;x<=n;x+=x&-x)
                for(int y2=lower_bound(bit[x].begin(),bit[x].end(),y)-bit[x].begin();y2<bit[x].size();y2+=y2&-y2){
                /// cout<<y2<<"\n";
                bit2[x][y2]+=z;}
    }

       int get(int x,int y)
         { int ss=0;
              for(x;x;x-=x&-x)
                for(int y2=lower_bound(bit[x].begin(),bit[x].end(),y)-bit[x].begin();y2;y2-=y2&-y2)
                  ss+=bit2[x][y2];
                  return ss;
         }
         void upd(int x, int y, int u, int v, int val) {
    up(x, y, val);
    up(x, v + 1, -val);
    up(u + 1, y, -val);
    up(u + 1, v + 1, val);
}
}cd;
vector<icd>v;
set<int> ss;
void phongbeo()
 {
     cin>>n>>m;
      cin>>s;
       for(int i=0;i<n;i++)
        if(s[i]=='0')
         ss.insert(i+1);
         ss.insert(n+1);
        ss.insert(0);
  for(int i=1;i<=m;i++)
  {
       string ss2;
       cin>>ss2;
        if(ss2[0]=='t'){cin>>l;

        if(s[l-1]=='1')s[l-1]='0';else s[l-1]='1';

  if(s[l-1]=='1')ss.erase(l);
    set<int>::iterator ss3 = ss.lower_bound(l);

    s3=*ss3;
    s3--;
    ss3--;
    s2=*ss3;
    s2++;
    if(s[l-1]=='0')ss.insert(l);
             if(s[l-1]=='0')
            cd.fake_upd(s2,l,l,s3,i),v.pb({s2,l,l,s3,i,0});
            else cd.fake_upd(s2,l,l,s3,-i),v.pb({s2,l,l,s3,-i,0});
        }
        else
        {
            cin>>l>>r;
            r--;
            cd.fake_get(l,r);
    set<int>::iterator ss3 = ss.lower_bound(l);
    s3=*ss3;
    if(s3>r)v.pb({l,r,i,0,0,1});
             else  v.pb({l,r,0,0,0,1});

        }
       }
     cd.setup();
      for(auto x:v)
        {
             if(x.f==0)
             {
                 cd.upd(x.a,x.b,x.c,x.d,x.e);
             }
             else
             {
                cout<<cd.get(x.a,x.b)+x.c,down
             }
        }
 }

Compilation message

street_lamps.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main()
      | ^~~~
street_lamps.cpp: In member function 'void BIT2D::fake_up(int, int, int)':
street_lamps.cpp:67:12: warning: statement has no effect [-Wunused-value]
   67 |        for(x;x<=n;x+=x&-x)
      |            ^
street_lamps.cpp: In member function 'void BIT2D::fake_get(int, int)':
street_lamps.cpp:74:19: warning: statement has no effect [-Wunused-value]
   74 |               for(x;x;x-=x&-x)
      |                   ^
street_lamps.cpp:73:16: warning: unused variable 'ss' [-Wunused-variable]
   73 |          { int ss=0;
      |                ^~
street_lamps.cpp: In member function 'void BIT2D::up(int, int, int)':
street_lamps.cpp:97:12: warning: statement has no effect [-Wunused-value]
   97 |        for(x;x<=n;x+=x&-x)
      |            ^
street_lamps.cpp:98:88: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for(int y2=lower_bound(bit[x].begin(),bit[x].end(),y)-bit[x].begin();y2<bit[x].size();y2+=y2&-y2){
      |                                                                                      ~~^~~~~~~~~~~~~~
street_lamps.cpp: In member function 'int BIT2D::get(int, int)':
street_lamps.cpp:105:19: warning: statement has no effect [-Wunused-value]
  105 |               for(x;x;x-=x&-x)
      |                   ^
street_lamps.cpp:106:17: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  106 |                 for(int y2=lower_bound(bit[x].begin(),bit[x].end(),y)-bit[x].begin();y2;y2-=y2&-y2)
      |                 ^~~
street_lamps.cpp:108:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |                   return ss;
      |                   ^~~~~~
street_lamps.cpp: In function 'void phongbeo()':
street_lamps.cpp:124:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  124 |         if(s[i]=='0')
      |         ^~
street_lamps.cpp:126:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  126 |          ss.insert(n+1);
      |          ^~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 74428 KB Output is correct
2 Correct 561 ms 103488 KB Output is correct
3 Correct 1251 ms 203692 KB Output is correct
4 Correct 3335 ms 416660 KB Output is correct
5 Correct 2883 ms 373488 KB Output is correct
6 Correct 3505 ms 457076 KB Output is correct
7 Correct 1439 ms 192024 KB Output is correct
8 Correct 1245 ms 183320 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15244 KB Output is correct
2 Correct 7 ms 14940 KB Output is correct
3 Correct 7 ms 14980 KB Output is correct
4 Correct 5 ms 14680 KB Output is correct
5 Runtime error 971 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14680 KB Output is correct
2 Correct 7 ms 14948 KB Output is correct
3 Correct 7 ms 15092 KB Output is correct
4 Correct 8 ms 15056 KB Output is correct
5 Correct 1765 ms 215644 KB Output is correct
6 Correct 3242 ms 350764 KB Output is correct
7 Correct 4471 ms 478592 KB Output is correct
8 Runtime error 1149 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 5 ms 14560 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14428 KB Output is correct
5 Correct 4 ms 14576 KB Output is correct
6 Correct 4 ms 14592 KB Output is correct
7 Correct 4 ms 14428 KB Output is correct
8 Correct 372 ms 74428 KB Output is correct
9 Correct 561 ms 103488 KB Output is correct
10 Correct 1251 ms 203692 KB Output is correct
11 Correct 3335 ms 416660 KB Output is correct
12 Correct 2883 ms 373488 KB Output is correct
13 Correct 3505 ms 457076 KB Output is correct
14 Correct 1439 ms 192024 KB Output is correct
15 Correct 1245 ms 183320 KB Output is correct
16 Correct 8 ms 15244 KB Output is correct
17 Correct 7 ms 14940 KB Output is correct
18 Correct 7 ms 14980 KB Output is correct
19 Correct 5 ms 14680 KB Output is correct
20 Runtime error 971 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -