oj.uz

Submission #1114202

# Submission time Handle Problem Language Result Execution time Memory
1114202 2024-11-18T10:58:46 Z SalihSahin Sličnost (COI23_slicnost) C++14
0 / 100
 1 ms 508 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){
      if(lazy[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;
         //cout<<l<<" "<<r<<" "<<ind<<" icin update geldi -> "<<tree[ind].first<<" "<<tree[ind].second<<endl;
      }
      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<<l<<" "<<r<<" "<<ind<<" icin update geldi -> "<<tree[ind].first<<" "<<tree[ind].second<<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);
   for(int i = 0; i < n; i++){
      int l = max(0LL, posp[i] - k + 1), r = min(n, posp[i] + k) - k;
      segp[i] = {l, r};
   }
   for(int i = 0; i < n; i++){
      int l = max(0LL, posq[i] - k + 1), r = min(n, posq[i] + k) - k;
      segq[i] = {l, r};
   }

   vector<array<int, 4> > updates;
   for(int i = 0; i < n; i++){
      updates.pb({segp[i].first, segq[i].first, segq[i].second, 1});
      updates.pb({segp[i].second + 1, segq[i].first, segq[i].second, -1});
   }
   sort(updates.begin(), updates.end());

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

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

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:107:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |       while(ind < updates.size() && updates[ind][0] <= i){
      |             ~~~~^~~~~~~~~~~~~~~~

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 508 KB Output is correct
4 Correct 1 ms 336 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 508 KB Output is correct
4 Correct 1 ms 336 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 508 KB Output is correct
4 Correct 1 ms 336 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 508 KB Output is correct
4 Correct 1 ms 336 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 508 KB Output is correct
4 Correct 1 ms 336 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 508 KB Output is correct
4 Correct 1 ms 336 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 -