oj.uz

Submission #568897

# Submission time Handle Problem Language Result Execution time Memory
568897 2022-05-26T10:23:00 Z almothana05 Street Lamps (APIO19_street_lamps) C++14
60 / 100
 444 ms 24168 KB 
#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

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.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 20788 KB Output is correct
2 Correct 227 ms 20808 KB Output is correct
3 Correct 234 ms 20748 KB Output is correct
4 Correct 311 ms 22944 KB Output is correct
5 Correct 266 ms 23200 KB Output is correct
6 Correct 282 ms 22840 KB Output is correct
7 Correct 309 ms 22720 KB Output is correct
8 Correct 340 ms 24168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 258 ms 22236 KB Output is correct
6 Correct 302 ms 22368 KB Output is correct
7 Correct 358 ms 22256 KB Output is correct
8 Correct 444 ms 23760 KB Output is correct
9 Correct 231 ms 12640 KB Output is correct
10 Correct 242 ms 20780 KB Output is correct
11 Correct 256 ms 20716 KB Output is correct
12 Correct 435 ms 22240 KB Output is correct
13 Correct 427 ms 23700 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 226 ms 20788 KB Output is correct
9 Correct 227 ms 20808 KB Output is correct
10 Correct 234 ms 20748 KB Output is correct
11 Correct 311 ms 22944 KB Output is correct
12 Correct 266 ms 23200 KB Output is correct
13 Correct 282 ms 22840 KB Output is correct
14 Correct 309 ms 22720 KB Output is correct
15 Correct 340 ms 24168 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 258 ms 22236 KB Output is correct
21 Correct 302 ms 22368 KB Output is correct
22 Correct 358 ms 22256 KB Output is correct
23 Correct 444 ms 23760 KB Output is correct
24 Correct 231 ms 12640 KB Output is correct
25 Correct 242 ms 20780 KB Output is correct
26 Correct 256 ms 20716 KB Output is correct
27 Correct 435 ms 22240 KB Output is correct
28 Correct 427 ms 23700 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Incorrect 1 ms 340 KB Output isn't correct
31 Halted 0 ms 0 KB -