Submission #568897

#	Time	Username	Problem	Language	Result	Execution time	Memory
568897		almothana05	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	444 ms	24168 KiB

street_lamps

#include<bits/stdc++.h>
#define mod 1000000007
#define inf 10000000000000000
using namespace std;
vector<int>num[200] , comp[3];
vector<string>ov;
vector<pair<int , int> >op;
int seg[2000000];


int sucher(int id , int l , int r , int gewl , int gewr){
   // cout << id << ' ' << l << ' ' << r << "\n";
   if(l > gewr || gewl > r){
      return -1;
   }
   if(gewl <= l && r <= gewr){
      // cout << l << ' ' << r << "\n\n";
      return seg[id];
   }
   int m = (l + r)/2;
   return max(sucher(id * 2 , l , m , gewl , gewr) , sucher(id * 2 + 1 , m + 1 , r , gewl , gewr));
}


int main(){
   // ios_base::sync_with_stdio(false);
   // cin.tie(NULL);
   string s;
   int menge , numm , nummer , ed , cmp , que ;;
   cin >> menge >> que;
   cin >> s;
   num[0].push_back(0);
   for(int i = 0 ; i < menge ; i++){
      num[0].push_back(num[0][i] + s[i] - '0');
   }
   if(menge <= 100 && que <= 100){
      for(int k = 0 ; k < que ; k++){
         string t;
         cin >> t >> numm;
         if(t == "query"){
            cin >> nummer;
            numm--;
            nummer--;
            int erg = 0;
            for(int i = k ; i >= 0 ; i--){
               erg += (num[i][nummer] - num[i][numm]) / (nummer - numm);
               // cout << erg << ' ';
            }
            cout << erg << "\n";
            for(int i = 0 ; i <= menge ; i++){
               num[k + 1].push_back(num[k][i]);
            }
         }
         else{
            // cout << s[numm - 1] << "\n";
            if(s[numm - 1] == '0'){
               s[numm - 1] = '1';
            }
            else{
               s[numm - 1] = '0';
            }
            // cout << s[numm - 1]<< "\n";
            num[k + 1].push_back(0);
            for(int i = 0 ; i < menge ; i++){
               num[k + 1].push_back(num[k + 1][i] + s[i] - '0');
               // cout << num[k + 1][i]<< ' ';
            } 
            // cout << "\n";
         }
      }
      return 0;
   }
   int fl = 1;
   for(int i = 0 ; i < que ; i++){
      string t;
      nummer = 0;
      cin >> t >> numm;
      if( t == "query" ){
         cin >> nummer;
         if(nummer - numm != 1){
            fl = 0;
         }
      }
      ov.push_back(t);
      op.push_back({numm , nummer});
   }
   if(fl == 0){
         
      int len;
      for(len = 1; len < menge ; len *= 2);
      for(int i = 0 ; i < menge ; i++){
         if(s[i] == '1'){
            seg[i + len] = 0;
         }
         else{
            seg[i + len] = mod;
         }
      }
      for(int i = menge ; i < len ; i++){
         seg[i + len] = mod;
      }
      for(int i = len - 1; i > 0 ; i--){
         seg[i] = max(seg[i * 2] , seg[i * 2 + 1]);
      }
      for(int k = 1 ; k <= que ; k++){
         string t;
         t = ov[k - 1];
         numm = op[k - 1].first;
         numm--;
         if(t == "query"){
            nummer = op[k - 1].second;
            nummer--;
            // cout << seg[2 + len] << "\n";
            cmp = sucher(1 , 1, len , numm + 1 , nummer );
            // cout << cmp << "\n";
            if(cmp == mod){
               cout << 0 << "\n";
               continue;
            }
            cout << k - cmp << "\n";
         }
         else{
            seg[numm + len] = k;
            for(int i = (numm + len) / 2 ; i > 0 ; i /= 2){
               seg[i] = max(seg[i * 2] , seg[i * 2 + 1]);
            }
         }
      }
      return 0;
   }

   for(int i = 0 ; i < menge;  i++){
      comp[0].push_back(0);
      comp[1].push_back(s[i] - '0');
      comp[2].push_back(0);
   }
   for(int k = 1 ; k <= que ; k++){
      string t; 
         t = ov[k - 1];
         numm = op[k - 1].first;
      if(t == "query"){
            nummer = op[k - 1].second;
         nummer--;
         numm--;
         if(comp[1][numm] == 1){
            cout << comp[0][numm] + (k - comp[2][numm]) << "\n";
         }
         else{
            cout << comp[0][numm] << "\n";
         }
      }
      else{
         numm--;
         if(comp[1][numm] == 1){
            comp[0][numm] += k - comp[2][numm] ;
            comp[1][numm] ^= 1;

         }
         else{
            comp[1][numm] ^= 1;
            comp[2][numm] = k;
         }
         // cout << comp[0][numm] << ' ' << comp[1][numm] << ' '<< comp[2][numm] << "\n";
      }
   }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:29:32: warning: unused variable 'ed' [-Wunused-variable]
   29 |    int menge , numm , nummer , ed , cmp , que ;;
      |                                ^~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20