제출 #1114264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114264		ljtunas	Poklon (COCI17_poklon)	C++14	140 / 140	1578 ms	19912 KiB

poklon

/****************************************
* author: _anhtun.hi_ (ig,tiktok,cf,..) *
*    mail:[email protected]      *
****************************************/
#pragma GCC optimize("O2")
#pragma GCC target("sse4.2")
#include                  <bits/stdc++.h>

using namespace           std;

#define fi                first
#define se                second
#define all(h)            h.begin(), h.end()
#define Log2(x)           (63 - __builtin_clzll(x))
#define Forv(v, h)        for(auto &v : h)
#define Rep(i, n)         for(int i = 1; i <= n; ++i)
#define For(i, a, b)      for(int i = a; i <= b; ++i)
#define Ford(i, a, b)     for(int i = a; i >= b; --i)
#define Bit(x, i)         ((x) >> (i) & 1ll)
#define onbit(x, i)       ((x) | (1ll << i))
#define offbit(x, i)      ((x) &~ (1ll << i))
#define cnt_bit(x)        __builtin_popcountll(x)
#define reset(h, v)       (memset(h, v, sizeof(h)))
#define memoryof(v)       (sizeof(v) / 1024 / 1024)

#define Time_run_code     (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)     if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}

using               ii  = pair<int, int>;
using               ull = unsigned long long;
using               db  = long double;
using               vi  = vector<int>;
using              vvi  = vector<vi>;
using              vii  = vector<ii>;

const int MAXN = 5e5  + 5;
const int base = 5e5 + 1;
const int MOD = 5e5 + 9;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}
 
template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

int n, Q, a[MAXN], Block;
int res[MAXN], cnt[MAXN];

struct Queries{
	int l, r, id;
};

vector <Queries> H;

void input() {};

void process() {
	int ans = 0;
	cin >> n >> Q;
	string num;
	For(i, 1, n) {
		int hash = 0;
		cin >> num;
		Forv(v, num) hash = ((hash << 1) + (hash << 3) + v - '0' + 1) % MOD;
		a[i] = hash;
		++cnt[a[i]];
		if (cnt[a[i]] == 2) ++ans;
		if (cnt[a[i]] == 3) --ans;
	}
	int u, v;
	For(i, 1, Q) cin >> u >> v, H.emplace_back(Queries{u, v, i});
	Block = sqrt(n);
	sort(all(H), [&](const Queries &x, const Queries &y){
		if (x.l / Block == y.l / Block) return x.r < y.r;
		return x.l / Block < y.l / Block;
	});
	function<void(int)> add = [&](int val) {
		++cnt[val];
		if (cnt[val] == 2) ++ans;
		if (cnt[val] == 3) --ans;
	};
	function<void(int)> remov = [&](int val) {
		--cnt[val];
		if (cnt[val] == 2) ++ans;
		if (cnt[val] == 1) --ans;
	};
	// solve
	int l = 1, r = n;
	Forv(tmp, H) {
		while (l < tmp.l) remov(a[l++]);
		while (l > tmp.l) add(a[--l]);
		while (r > tmp.r) remov(a[r--]);
		while (r < tmp.r) add(a[++r]);
		res[tmp.id] = ans;
	}
	For(i, 1, Q) cout << res[i] << '\n';
};

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //_______________________________
    file("Poklon");
    input();
    process();
    cerr << "Time elapsed: " << Time_run_code << " s.\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

poklon.cpp: In function 'int main()':
poklon.cpp:27:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 | #define file(name)     if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:106:5: note: in expansion of macro 'file'
  106 |     file("Poklon");
      |     ^~~~
poklon.cpp:27:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 | #define file(name)     if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:106:5: note: in expansion of macro 'file'
  106 |     file("Poklon");
      |     ^~~~

• Subtask 1: 140 / 140