Submission #884823

#	Time	Username	Problem	Language	Result	Execution time	Memory
884823		Nursik	Lottery (CEOI18_lot)	C++14	100 / 100	679 ms	8784 KiB

lot

#include <stdio.h>
  
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <random>
#include <chrono>
#include <queue>
#include <functional>
#include <iostream>
#include <queue>
//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
  
const ll maxn = 1e4 + 1, maxm = 2e3 + 1;
    const ll mod = 1e9 + 7, mod2 = 998244353, inf = 1e9, block = 550, hb = 1000012337, base = 37, sq = 500;
const ld eps = 1e-3;
  
int n, l, q, k;
int a[maxn];
unsigned short dp[maxn], pdp[maxn], ans[maxn], is[maxn];
short go[maxn + 1];
unsigned short answ[maxn][105], answw[maxn][105];
vector<unsigned short> kek[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);    
  //  assert(0);
    cin >> n >> l;
    for (int i = 0; i <= l; ++i){
        go[i] = -1;
    }
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    cin >> q;
    vector<pair<unsigned short, short>> query;
    for (int i = 1; i <= q; ++i){
        cin >> k;
        query.pb(mp(k, i));
    }
    sort(query.begin(), query.end());
    for (auto it : query){
        is[it.f] = it.s;
    }
    for (int i = l; i >= 0; --i){
        if (is[i]){
            go[i] = is[i];
        }
        else{
            if (i + 1 <= l){
                go[i] = go[i + 1];
            }
        }
    }
   // cout << l << '\n';
   // for (int i = 0; i <= l; ++i){
     //   assert(go[i] <= l);
    //}
    for (int i = n; i >= 1; --i){
        for (int j = n; j >= 1; --j){
            dp[j] = pdp[j + 1];
            if (i + l <= n && j + l <= n){
                dp[j] -= (a[i + l] != a[j + l]);
            }

            dp[j] += (a[i] != a[j]);

            if (j + l  - 1 <= n && i + l - 1 <= n && i != j){
                if (go[dp[j]] != -1){
                 //   assert(go[dp[j]] <= 100);
                 //   assert(i <= n);
                    answ[i][go[dp[j]]] += 1;
                }
            }
        }
        for (int j = n; j >= 1; --j){
            pdp[j] = dp[j];
        }
    }

    for (int i = 0; i < q; ++i){
        if (i > 0 && query[i].f == query[i - 1].f){
            for (int j = 1; j <= n; ++j){
                answw[j][query[i].s] = answw[j][query[i - 1].s];
            }
            continue;
        }
        for (int j = 1; j <= n; ++j){
            if (go[query[i].f] != -1){
               // assert(go[query[i].f] <= l);
            //    assert(query[i].s <= q);
                answw[j][query[i].s] += answ[j][go[query[i].f]];
            }
            if (i > 0){
                answw[j][query[i].s] += answw[j][query[i - 1].s];
            }
        }
    }
    for (int i = 1; i <= q; ++i){
        for (int j = 1; j <= n - l + 1; ++j){
            cout << answw[j][i] << " ";
        }
        cout << '\n';
    }
}

/*
a.cpp:103:21: runtime error: index 101 out of bounds for type 'unsigned short[101]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior a.cpp:103:21 in 
a.cpp:120:37: runtime error: index 101 out of bounds for type 'unsigned short[101]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior a.cpp:120:37 in 
 */

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20