| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55381 |
2018-07-07T06:02:18 Z |
윤교준(#1546) |
Employment (JOI16_employment) |
C++11 |
|
5000 ms |
12472 KB |
#include <bits/stdc++.h>
#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;
const bool debug = false;
const int MAXN = 200005;
const int MAXQ = 200005;
const int SQRN = 485;
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+SQRN && qi <= Q; qi++) {
if(2 != B[qi]) continue;
int bi = (C[qi]-1)/SQRN + 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]);
}
}
}
for(int i = 1; i <= bukn; i++) buk[i].cal();
{
vector<pii> V;
for(int qi = qs; qi < qs+SQRN && 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)/SQRN + 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(debug) freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin >> N >> Q;
for(int i = 1; i <= N; i++) cin >> A[i];
for(int i = 1; i <= Q; i++) {
cin >> B[i] >> 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)*SQRN+1;
e = min(N, bi*SQRN);
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 % SQRN) {
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:79:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int v : XV) printf("%d ", v); puts("");
^~~
employment.cpp:79: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:169:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
if(debug) freopen("input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5029 ms |
2296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3432 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3432 KB |
Output is correct |
| 3 |
Correct |
7 ms |
3576 KB |
Output is correct |
| 4 |
Correct |
58 ms |
4436 KB |
Output is correct |
| 5 |
Correct |
185 ms |
5836 KB |
Output is correct |
| 6 |
Correct |
502 ms |
6388 KB |
Output is correct |
| 7 |
Correct |
1390 ms |
8736 KB |
Output is correct |
| 8 |
Correct |
2089 ms |
9800 KB |
Output is correct |
| 9 |
Execution timed out |
5058 ms |
12472 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5029 ms |
2296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
