Submission #568886

#	Time	Username	Problem	Language	Result	Execution time	Memory
568886		almothana05	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	915 ms	8076 KiB

street_lamps

#include<bits/stdc++.h>
#define mod 1000000007
#define inf 10000000000000000
using namespace std;
vector<int>num[200] , comp[3];
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 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;
      cin >> t >> numm;
      numm--;
      if(t == "query"){
         cin >> nummer;
         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; 
      cin >> t >> numm;
      if(t == "query"){
         cin >> nummer;
         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:27:32: warning: unused variable 'ed' [-Wunused-variable]
   27 |    int menge , numm , nummer , ed , cmp , que ;;
      |                                ^~

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