oj.uz

Submission #121760

# Submission time Handle Problem Language Result Execution time Memory
121760 2019-06-27T04:24:57 Z _7_7_ Lottery (CEOI18_lot) C++14
35 / 100
 405 ms 8668 KB 
#include <bits/stdc++.h>                                           

//#define int long long	
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);                                          
#define forev(i, b, a) for(int i = (b); i >= (a); --i)	    
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define sz(s) (int)s.size()
#define all(x) x.bg, x.en                                                                    
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define rbg rbegin()
#define bg begin()
#define en end()
#define s second
#define f first                                               
	
   
using namespace std;                  
   
   
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb; 
typedef long long ll;  
typedef double db;                            
						               
				
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 265;	
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);  
const int inf = 1e9, N = 1e4 + 11, mod = 1e9 + 7;
const db eps = 1e-12, pi = 3.14159265359; 
const ll INF = 1e18;	


int n, l, a[N], q, pos[N], c[N], add[N][104], res[N][104];
pii b[N];


main () {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);                                        
	cout.tie(0);
	cin >> n >> l;
	forn (i, 1, n)
		cin >> a[i];                  

	cin >> q;
	forn (i, 1, q) {
		cin >> b[i].f;
		b[i].s = i;
	}

	sort(b + 1, b + 1 + q);
	b[0].f = -1;
	forn (i, 0, n)
		c[i] = q + 1;
	forn (i, 1, q) {
		pos[b[i].s] = i;
		forn (x, b[i - 1].f + 1, b[i].f)
			c[x] = i;						
	}


	forn (d, 1, n - l) {
		int cur = 0;
		forn (i, 1, l - 1)
			cur += (a[i] != a[i + d]);
		forn (i, l, n - d) {
			cur += (a[i] != a[i + d]);
			++add[i - l + 1][c[cur]];			
			++add[i + d - l + 1][c[cur]];
//			cout << i << ' ' << i + d << ' ' << cur << ' ' << c[cur] << endl;
			cur -= (a[i - l + 1] != a[i - l + 1 + d]);
		}
	}

	forn (i, 1, q) 
		forn (j, 1, n)
			res[j][i] = res[j][i - 1] + add[j][i];
	
	forn (i, 1, q) {
		forn (j, 1, n - l + 1)
			cout << res[j][b[i].s] << ' '; 
		cout << endl;		
	}
	return 0;
}

Compilation message

lot.cpp:47:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 8668 KB Output is correct
2 Correct 390 ms 8644 KB Output is correct
3 Correct 366 ms 8540 KB Output is correct
4 Correct 375 ms 8568 KB Output is correct
5 Correct 111 ms 6520 KB Output is correct
6 Correct 336 ms 8312 KB Output is correct
7 Correct 117 ms 6604 KB Output is correct
8 Correct 205 ms 7428 KB Output is correct
9 Correct 339 ms 8504 KB Output is correct
10 Correct 374 ms 8560 KB Output is correct
11 Correct 16 ms 2432 KB Output is correct
12 Correct 209 ms 6904 KB Output is correct
13 Correct 153 ms 6904 KB Output is correct
14 Correct 153 ms 6852 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 8668 KB Output is correct
2 Correct 390 ms 8644 KB Output is correct
3 Correct 366 ms 8540 KB Output is correct
4 Correct 375 ms 8568 KB Output is correct
5 Correct 111 ms 6520 KB Output is correct
6 Correct 336 ms 8312 KB Output is correct
7 Correct 117 ms 6604 KB Output is correct
8 Correct 205 ms 7428 KB Output is correct
9 Correct 339 ms 8504 KB Output is correct
10 Correct 374 ms 8560 KB Output is correct
11 Correct 16 ms 2432 KB Output is correct
12 Correct 209 ms 6904 KB Output is correct
13 Correct 153 ms 6904 KB Output is correct
14 Correct 153 ms 6852 KB Output is correct
15 Correct 353 ms 8508 KB Output is correct
16 Correct 297 ms 8236 KB Output is correct
17 Correct 383 ms 8568 KB Output is correct
18 Correct 405 ms 8568 KB Output is correct
19 Correct 377 ms 8568 KB Output is correct
20 Correct 394 ms 8568 KB Output is correct
21 Correct 385 ms 8476 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -