oj.uz

Submission #121749

# Submission time Handle Problem Language Result Execution time Memory
121749 2019-06-27T04:16:04 Z _7_7_ Lottery (CEOI18_lot) C++14
35 / 100
 398 ms 8572 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][102], res[N][102];
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, 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 + 1) {
		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 387 ms 8440 KB Output is correct
2 Correct 366 ms 8424 KB Output is correct
3 Correct 372 ms 8428 KB Output is correct
4 Correct 377 ms 8440 KB Output is correct
5 Correct 110 ms 6520 KB Output is correct
6 Correct 334 ms 8284 KB Output is correct
7 Correct 109 ms 6492 KB Output is correct
8 Correct 190 ms 7392 KB Output is correct
9 Correct 361 ms 8444 KB Output is correct
10 Correct 346 ms 8416 KB Output is correct
11 Correct 17 ms 2432 KB Output is correct
12 Correct 197 ms 7004 KB Output is correct
13 Correct 149 ms 6900 KB Output is correct
14 Correct 140 ms 6904 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 8440 KB Output is correct
2 Correct 366 ms 8424 KB Output is correct
3 Correct 372 ms 8428 KB Output is correct
4 Correct 377 ms 8440 KB Output is correct
5 Correct 110 ms 6520 KB Output is correct
6 Correct 334 ms 8284 KB Output is correct
7 Correct 109 ms 6492 KB Output is correct
8 Correct 190 ms 7392 KB Output is correct
9 Correct 361 ms 8444 KB Output is correct
10 Correct 346 ms 8416 KB Output is correct
11 Correct 17 ms 2432 KB Output is correct
12 Correct 197 ms 7004 KB Output is correct
13 Correct 149 ms 6900 KB Output is correct
14 Correct 140 ms 6904 KB Output is correct
15 Correct 359 ms 8312 KB Output is correct
16 Correct 322 ms 8080 KB Output is correct
17 Correct 398 ms 8496 KB Output is correct
18 Correct 377 ms 8440 KB Output is correct
19 Correct 371 ms 8572 KB Output is correct
20 Correct 393 ms 8452 KB Output is correct
21 Correct 381 ms 8460 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 -