oj.uz

Submission #1114214

# Submission time Handle Problem Language Result Execution time Memory
1114214 2024-11-18T11:27:44 Z SalihSahin Sličnost (COI23_slicnost) C++14
0 / 100
 1 ms 504 KB 
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
 
const int inf = 1e15 + 10;
const int N = 2048 + 10;

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
   if(a.first == b.first) return {a.first, a.second + b.second};
   else if(a.first > b.first) return a;
   else return b;
}

struct SEGT{
   vector<pair<int, int> > tree;
   vector<int> lazy;

   void init(int n){
      tree.assign(4*n, {0, 1});
      lazy.assign(4*n, 0);
   }

   void build(int ind, int l, int r){
      if(l == r){
         tree[ind] = {0, 1};
      }
      else{
         int m = (l + r)/2;

         build(ind*2, l, m);
         build(ind*2, m+1, r);
         tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
      }
   }

   void push(int ind){
      lazy[ind*2] += lazy[ind];
      tree[ind*2].first  += lazy[ind];
      lazy[ind*2+1] += lazy[ind];
      tree[ind*2+1].first += lazy[ind];
      lazy[ind] = 0;
   }

   void update(int ind, int l, int r, int ql, int qr, int val){
      if(l > r || l > qr || r < ql) return;
      if(l >= ql && r <= qr){
         tree[ind].first += val;
         lazy[ind] += val;
      }
      else{
         int m = (l + r)/2;
         push(ind);

         update(ind*2, l, m, ql, qr, val);
         update(ind*2+1, m+1, r, ql, qr, val);

         tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
         //cout<<ind<<" icin => "<<tree[ind*2].first<<" "<<tree[ind*2].second<<" ve "<<tree[ind*2+1].first<<" "<<tree[ind*2+1].second<<" mergelendi"<<endl;
      }
   }
};
 
int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);
   int n, k, query;
   cin>>n>>k>>query;
   vector<int> p(n), q(n), posp(n), posq(n);
   for(int i = 0; i < n; i++){
      cin>>p[i];
      p[i]--;
      posp[p[i]] = i;
   }
   for(int i = 0; i < n; i++){
      cin>>q[i];
      q[i]--;
      posq[q[i]] = i;
   }

   vector<pair<int, int> > segp(n), segq(n);
   int l, r;
   vector<array<int, 3> > updates[n+1];
   for(int i = 0; i < n; i++){
      l = max(0LL, posp[i] - k + 1), r = min(n, posp[i] + k) - k;
      segp[i] = {l, r};

      l = max(0LL, posq[i] - k + 1), r = min(n, posq[i] + k) - k;
      segq[i] = {l, r};

      updates[segp[i].first].pb({segq[i].first, segq[i].second, 1});
      updates[segp[i].second + 1].pb({segq[i].first, segq[i].second, -1});
   }

   pair<int, int> ans = {0, 0};
   SEGT seg;
   seg.init(n);
   seg.build(1, 1, n);
   for(int i = 0; i < n; i++){
      for(auto itr: updates[i]){
         seg.update(1, 1, n, itr[0] + 1, itr[1] + 1, itr[2]);
         //cout<<"i = "<<i<<" update => "<<itr[0]+1<<" "<<itr[1]+1<<" araligina "<<itr[2]<<endl;
      }
      //cout<<i<<" -> "<<seg.tree[1].first<<" "<<seg.tree[1].second<<endl;
      ans = merge(ans, seg.tree[1]);
   }

   cout<<ans.first<<" "<<ans.second<<endl;
   return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -