제출 #1114218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114218		SalihSahin	Sličnost (COI23_slicnost)	C++14	50 / 100	145 ms	26308 KiB

Main

#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, 0});
      lazy.assign(4*n, 0);
   }

   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 == r){
         tree[ind].first += val;
         tree[ind].second = 1;
      }
      else 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);
   for(int i = 1; i <= n; i++){
      seg.update(1, 1, n, i, i, 0);
   }
   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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 33 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33