| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55383 |
2018-07-07T06:11:44 Z |
윤교준(#1546) |
Employment (JOI16_employment) |
C++11 |
|
5000 ms |
19072 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
int rd(int s, int e) { return rand()%(e-s+1) + s; }
static unsigned char str[55000055], *p = str;
const bool debug = false;
const int MAXN = 200005;
const int MAXQ = 200005;
const int SQRN = 515;
int YI[SQRN][SQRN];
int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];
int N, Q;
struct BUK {
set<pii> O;
vector<int> XV;
int cnt[SQRN*2];
int S, E;
void clear() {
XV.clear();
}
void calcnt() {
auto it = O.begin();
int vn = sz(XV), n = 0, l = 0;
for(int vi = vn-1, y; 0 <= vi; vi--) {
y = XV[vi];
for(int i; O.end() != it; it++) {
i = it -> second;
if(A[i] < y) break;
n++;
if(S < i && y <= A[i-1]) l++;
if(i < E && y < A[i+1]) l++;
if(debug) {
printf("vn=%d, vi=%d, y=%d : n=%d, l=%d\n", vn, vi, y, n, l);
}
}
cnt[vi] = n-l;
}
}
void cal() {
calcnt();
}
int get(int y) {
if(y < 0 || sz(XV) <= y) return 0;
return cnt[y];
}
void upd(int idx, int x, int y) {
O.erase(pii(-x, idx));
O.insert(pii(-y, idx));
calcnt();
}
void print() {
puts("BUK INF");
for(int v : XV) printf("%d ", v); puts("");
for(int i = 0; i < sz(XV); i++) printf("%d ; %d\n", i, cnt[i]);
puts("BUK INF END");
}
} buk[SQRN]; int bukn;
vector<int> QXV[SQRN];
void initbuk(int qs) {
for(int bi = 1; bi <= bukn; bi++) {
QXV[bi].clear();
buk[bi].clear();
}
for(int qi = qs; qi < qs+512 && qi <= Q; qi++) {
if(2 != B[qi]) continue;
int bi = ((C[qi]-1)>>9) + 1;
QXV[bi].pb(D[qi]);
}
for(int bi = 1; bi <= bukn; bi++) {
vector<int> V;
for(auto &v : buk[bi].O)
V.pb(-v.first);
revv(V); univ(V);
sorv(QXV[bi]); univ(QXV[bi]);
vector<int> &T = buk[bi].XV;
for(int a = 0, b = 0, an = sz(V), bn = sz(QXV[bi]); a < an || b < bn;) {
if(a < an && (b == bn || V[a] <= QXV[bi][b])) {
if(T.empty() || T.back() != V[a]) T.pb(V[a]);
a++;
} else {
if(T.empty() || T.back() != QXV[bi][b])
T.pb(QXV[bi][b]);
b++;
}
}
}
for(int i = 1; i <= bukn; i++) buk[i].cal();
{
vector<pii> V;
for(int qi = qs; qi < qs+512 && qi <= Q; qi++) {
if(1 == B[qi]) V.eb(C[qi], qi);
else V.eb(D[qi], qi);
}
sorv(V);
for(int bi = 1; bi <= bukn; bi++) {
int i = 0, n = sz(buk[bi].XV);
for(auto &v : V) {
int idx, y; tie(y, idx) = v;
for(; i < n && buk[bi].XV[i] < y; i++);
YI[idx-qs][bi] = i;
}
}
}
if(debug) {
buk[1].print();
}
}
void upd(int x, int y) {
int bi = ((x-1)>>9) + 1;
int bf = A[x];
A[x] = y;
buk[bi].upd(x, bf, y);
}
int CC[SQRN];
int getAns(int qs, int qi, int y) {
if(debug) printf("getAns y=%d\n", y);
int ret = 0;
for(int bi = 1, s, e; bi <= bukn; bi++) {
s = buk[bi].S; e = buk[bi].E;
CC[bi] = buk[bi].get(YI[qi-qs][bi]);
ret += CC[bi];
if(1 < bi && y <= A[s-1] && y <= A[s])
ret--;
if(debug) printf("bi=%d, s=%d, e=%d : ret=%d\n", bi, s, e, ret);
}
if(debug) printf("FINAL ret=%d\n", ret);
return ret;
}
int main() {
if(0) {
freopen("output.txt", "w", stdout);
srand(time(0));
puts("200000 200000");
for(int i = 0; i < 200000; i++)
printf("%d\n", rd(1, 1000000000));
for(int i = 0; i < 200000; i++) {
if(rd(0, 1)) {
printf("1 %d\n", rd(1, 1000000000));
} else {
printf("2 %d %d\n", rd(1, 200000), rd(1, 1000000000));
}
}
return 0;
}
//freopen("output.txt", "r", stdin);
//freopen("tmp.txt", "w", stdout);
fread(str, 1, 55000055, stdin);
rf(N) rf(Q)
for(int i = 1; i <= N; i++) { rf(A[i]); }
for(int i = 1; i <= Q; i++) {
rf(B[i]) rf(C[i])
if(2 == B[i]) cin >> D[i];
}
{
vector<int> V;
for(int i = 1; i <= N; i++) V.pb(A[i]);
for(int i =1 ; i <= Q; i++)
V.pb(1 == B[i] ? C[i] : D[i]);
sorv(V); univ(V);
for(int i = 1; i <= N; i++)
A[i] = (int)(lower_bound(allv(V), A[i]) - V.begin()) + 1;
for(int i = 1; i <= Q; i++) {
if(1 == B[i])
C[i] = (int)(lower_bound(allv(V), C[i]) - V.begin()) + 1;
else
D[i] = (int)(lower_bound(allv(V), D[i]) - V.begin()) + 1;
}
}
if(debug) {
for(int i = 1; i <= N; i++)
printf("%d ", A[i]);
puts("");
for(int i = 1; i <= Q; i++)
printf("Q %d : %d %d %d\n", i, B[i], C[i], D[i]);
}
for(int bi = 1, s, e;; bi++) {
s = ((bi-1)<<9)+1;
e = min(N, bi<<9);
if(s > e) break;
buk[bi].S = s;
buk[bi].E = e;
for(int i = s; i <= e; i++)
buk[bi].O.insert(pii(-A[i], i));
bukn = bi;
}
for(int qi = 1, qs = 1; qi <= Q; qi++) {
if(1 == (qi & 511)) {
qs = qi;
initbuk(qi);
}
if(1 == B[qi]) {
printf("%d\n", getAns(qs, qi, C[qi]));
} else {
upd(C[qi], D[qi]);
}
}
return 0;
}
Compilation message
employment.cpp: In member function 'void BUK::print()':
employment.cpp:82:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int v : XV) printf("%d ", v); puts("");
^~~
employment.cpp:82:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int v : XV) printf("%d ", v); puts("");
^~~~
employment.cpp: In function 'int main()':
employment.cpp:174:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("output.txt", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
employment.cpp:191:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(str, 1, 55000055, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3816 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3872 KB |
Output is correct |
| 4 |
Correct |
53 ms |
5004 KB |
Output is correct |
| 5 |
Correct |
196 ms |
6776 KB |
Output is correct |
| 6 |
Correct |
431 ms |
7932 KB |
Output is correct |
| 7 |
Correct |
998 ms |
10668 KB |
Output is correct |
| 8 |
Correct |
1558 ms |
12120 KB |
Output is correct |
| 9 |
Correct |
3525 ms |
16228 KB |
Output is correct |
| 10 |
Correct |
4032 ms |
18748 KB |
Output is correct |
| 11 |
Execution timed out |
5054 ms |
19072 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
