| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 799897 |
2023-08-01T07:51:50 Z |
반딧불(#10081) |
Harvest (JOI20_harvest) |
C++17 |
|
301 ms |
86028 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void input();
void getPersonInfo();
void organizeTree();
void getAppleInfo();
void inputQuery();
void solve();
void output();
int main(){
input();
getPersonInfo();
organizeTree();
getAppleInfo();
inputQuery();
solve();
output();
}
int n, k, q; ll L, C;
ll a[200002], b[200002];
void input(){
scanf("%d %d %lld %lld", &n, &k, &L, &C);
for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
for(int i=1; i<=k; i++) scanf("%lld", &b[i]);
}
int nxt[200002]; ll delay[200002];
int par[200002]; bool inCycle[200002]; /// inCycle�� 0�� ��츸 par�� 0�� �ƴϴ�
ll dist[200002];
int cycleNum[200002], cycleIdx[200002];
vector<int> cycle[200002]; /// ����Ŭ�� ��� ���
vector<ll> cycleT[200002]; /// ���������� �� �������� ��ȸ�ϴ� �� �ɸ��� �ð�
ll cycleLength[200002]; /// �� ����Ŭ�� �ѷ�
int findNxt(ll t){ /// t ������ �
int idx = upper_bound(a+1, a+n+1, t) - a - 1;
if(idx == 0) idx = n;
return idx;
}
ll findNxtTime(ll s, ll mod){
return (s-mod+L-1)/L*L+mod;
}
void getPersonInfo(){
for(int i=1; i<=n; i++){
nxt[i] = findNxt((a[i]-C%L+L)%L);
delay[i] = findNxtTime(C, (a[i] - a[nxt[i]] + L) % L);
}
vector<int> visited (n+1);
for(int i=1; i<=n; i++){
if(visited[i]) continue;
vector<int> history;
int x = i; ll timeSum = 0;
while(true){
if(visited[x]){ /// ��
if(visited[x] == i){ /// ���ο� ����Ŭ�� ã�Ҵ�
int idx = find(history.begin(), history.end(), x) - history.begin();
/// [idx, end) �κ��� �׳� ����Ŭ�� ������ �ȴ�
for(int i=idx; i<(int)history.size(); i++){
cycle[x].push_back(history[i]);
cycleT[x].push_back(cycleLength[x]);
cycleNum[history[i]] = x, cycleIdx[history[i]] = i-idx, inCycle[history[i]] = true;
cycleLength[x] += delay[history[i]];
}
/// �κ��� �׳� Ʈ��
int pr = x;
for(int i=idx-1; i>=0; i--){
par[history[i]] = pr, dist[history[i]] = dist[pr] + delay[history[i]];
cycleNum[history[i]] = cycleNum[pr], cycleIdx[history[i]] = cycleIdx[pr];
pr = history[i];
}
}
else{ /// �׳� Ʈ�� �Ϻκ��� ã�Ҵ�
int pr = x;
for(int i=(int)history.size()-1; i>=0; i--){
par[history[i]] = pr, dist[history[i]] = dist[pr] + delay[history[i]];
cycleNum[history[i]] = cycleNum[pr], cycleIdx[history[i]] = cycleIdx[pr];
pr = history[i];
}
}
break;
}
visited[x] = i;
history.push_back(x);
timeSum += delay[x], x = nxt[x];
}
}
#ifdef TEST
printf("Person info done\n");
for(int i=1; i<=n; i++){
printf("%d: ", i);
if(inCycle[i]) printf("in cycle, %d - %dth, dist %lld\n", cycleNum[i], cycleIdx[i], cycleT[cycleNum[i]][cycleIdx[i]]);
else printf("in tree, par %d, dist %lld\n", par[i], dist[i]);
}
#endif // TEST
}
vector<int> child[200002];
int depth[200002], LCADB[200002][20];
void dfs(int x){
for(auto y: child[x]){
depth[y] = depth[x] + 1, par[y] = LCADB[y][0] = x;
dfs(y);
}
}
void organizeTree(){
for(int i=1; i<=n; i++){
if(par[i]) child[par[i]].push_back(i);
}
for(int i=1; i<=n; i++){
if(inCycle[i]) dfs(i);
}
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
}
int appleTo[200002]; ll appleDelay[200002];
void getAppleInfo(){
for(int i=1; i<=k; i++){
appleTo[i] = findNxt(b[i]);
appleDelay[i] = (b[i] - a[appleTo[i]] + L) % L;
}
#ifdef TEST
puts("Apple info");
for(int i=1; i<=k; i++) printf("%d: to %d, delay %lld\n", i, appleTo[i], appleDelay[i]);
#endif // TEST
}
/// ���� �Է��ϴ� �κ�
struct Query{
int idx, x; ll t;
Query(){}
Query(int idx, int x, ll t): idx(idx), x(x), t(t){}
};
vector<Query> queries[200002];
void inputQuery(){
scanf("%d", &q);
for(int i=1; i<=q; i++){
Query p;
p.idx = i;
scanf("%d %lld", &p.x, &p.t);
queries[p.x].push_back(p);
}
}
/// �� �Ʒ����� ������ ó���Ѵ�.
int getLCA(int x, int y){
if(depth[x] > depth[y]) swap(x, y);
for(int d=0; d<20; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
if(x==y) return x;
for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
return par[x];
}
int kthParent(int x, int k){
for(int d=0; d<20; d++) if((k>>d)&1) x = LCADB[x][d];
return x;
}
struct MergeSortTree{
vector<ll> tree[1<<19];
void init(int i, int l, int r, ll *A){
if(l==r){
tree[i] = vector<ll> (1, A[l]);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i].resize(tree[i*2].size() + tree[i*2+1].size());
merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
}
ll query(int i, int l, int r, int s, int e, ll v){
if(r<s || e<l) return 0;
if(s<=l && r<=e){
return upper_bound(tree[i].begin(), tree[i].end(), v) - tree[i].begin();
}
int m = (l+r)>>1;
return query(i*2, l, m, s, e, v) + query(i*2+1, m+1, r, s, e, v);
}
} mst;
vector<int> appleList[200002]; /// �� �������� �����ϴ� ��� ����
ll ans[200002];
int in[200002], out[200002], inCnt;
ll mstVal[200002];
void dfs1_search(int x){
in[x] = inCnt + 1;
for(auto p: appleList[x]){
mstVal[++inCnt] = dist[x] + appleDelay[p];
}
for(auto y: child[x]){
dfs1_search(y);
}
out[x] = inCnt;
}
void dfs1_answer(int x){
if(!inCycle[x] && in[x] <= out[x]) for(Query &p: queries[x]){
ans[p.idx] += mst.query(1, 1, inCnt, in[x], out[x], p.t + dist[p.x]);
}
for(auto p: child[x]){
dfs1_answer(p);
}
}
void solveCase1(int root){ /// Ʈ�� -> Ʈ���� �ذ��ϴ� �Լ�
/// delay[i] + dist[i] <= t + dist[x]���� �����ϴٴ� ���� �̿���
inCnt = 0;
dfs1_search(root);
if(!inCnt) return;
mst.init(1, 1, inCnt, mstVal);
dfs1_answer(root);
}
/// �� �Ʒ����� case 2
struct Fenwick{
int n;
ll tree[200002];
void init(int _n){
n = _n;
for(int i=0; i<=n; i++) tree[i] = 0;
}
void add(int x, ll v){
while(x<=n){
tree[x] += v;
x += x&-x;
}
}
ll sum(int x){
ll ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret;
}
ll sum(int l, int r){
if(l>r) return 0;
return sum(r) - sum(l-1);
}
} fenwick;
struct lazySegmentTree{
ll sum[1<<19], lazy[1<<19];
int cnt[1<<19];
void init(int i, int l, int r){
sum[i] = lazy[i] = cnt[i] = 0;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
sum[i] += lazy[i] * cnt[i];
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int x){
propagate(i, l, r);
if(l==r){
sum[i]++, cnt[i]++;
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x), propagate(i*2+1, m+1, r);
else update(i*2+1, m+1, r, x), propagate(i*2, l, m);
sum[i] = sum[i*2] + sum[i*2+1], cnt[i] = cnt[i*2] + cnt[i*2+1];
}
void update(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
sum[i] = sum[i*2] + sum[i*2+1], cnt[i] = cnt[i*2] + cnt[i*2+1];
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e) return sum[i];
int m = (l+r)>>1;
return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
}
} segtree;
struct Event{
int type; /// 0�̸� �� ����, 1�̸� ����
ll val;
int idx;
Event(int type, ll val, int idx): type(type), val(val), idx(idx){}
bool operator<(const Event &r)const{
if(val != r.val) return val < r.val;
else return type < r.type;
}
};
vector<ll> puttingNumber[200002];
void solveCase2(int g){ /// ����Ŭ -> ����Ŭ�� �ذ��ϴ� �Լ�
int s = (int)cycle[g].size();
const ll MOD = cycleLength[g];
/// ���� ���������� ���� �� �κп� ���ؼ��� �غ�
/// ����� ���� �������� ��� ����
{
vector<ll> renumber(1, -1e18);
for(int i=1; i<s; i++){
int x = cycle[g][i];
for(int p: appleList[x]){
ll v = appleDelay[p] - cycleT[g][i];
puttingNumber[i].push_back(v);
renumber.push_back(v);
}
}
sort(renumber.begin(), renumber.end());
renumber.erase(unique(renumber.begin(), renumber.end()), renumber.end());
int r = (int)renumber.size() - 1;
fenwick.init(r);
for(int i=1; i<s; i++){
for(ll p: puttingNumber[i]){
int idx = lower_bound(renumber.begin(), renumber.end(), p) - renumber.begin();
fenwick.add(idx, 1);
}
for(Query p: queries[cycle[g][i]]){
int idx = upper_bound(renumber.begin(), renumber.end(), p.t - cycleT[g][i]) - renumber.begin() - 1;
ans[p.idx] += fenwick.sum(1, idx);
}
}
}
/// �״��� ������������ ���� �ð��� ��� �����
vector<ll> renumber;
vector<Event> timeline;
for(int i=0; i<s; i++){
int x = cycle[g][i];
for(int p: appleList[x]){
ll v = appleDelay[p] + (i == 0 ? 0 : cycleLength[g] - cycleT[g][i]);
renumber.push_back(v % MOD);
timeline.push_back(Event(0, v, 0));
}
for(Query p: queries[x]){
ll v = p.t - (i == 0 ? 0 : cycleT[g][i]);
if(v<0) continue;
timeline.push_back(Event(1, v, p.idx));
renumber.push_back(v % MOD);
}
}
sort(renumber.begin(), renumber.end());
renumber.erase(unique(renumber.begin(), renumber.end()), renumber.end());
sort(timeline.begin(), timeline.end());
int r = (int)renumber.size();
if(!r) return;
segtree.init(1, 0, r-1);
ll lastT = 0;
for(Event p: timeline){
if(lastT != p.val){ /// �ð��� ������Ʈ
ll a1 = lastT / cycleLength[g], b1 = lastT % MOD;
ll a2 = p.val / cycleLength[g], b2 = p.val % MOD;
int idx1 = lower_bound(renumber.begin(), renumber.end(), b1) - renumber.begin() + 1;
int idx2 = lower_bound(renumber.begin(), renumber.end(), b2) - renumber.begin();
if(a1 == a2){
segtree.update(1, 0, r-1, idx1, idx2, 1);
}
else{
segtree.update(1, 0, r-1, idx1, r-1, 1);
if(a2-a1>1) segtree.update(1, 0, r-1, 0, r-1, a2-a1-1);
segtree.update(1, 0, r-1, 0, idx2, 1);
}
lastT = p.val;
}
int idx = lower_bound(renumber.begin(), renumber.end(), p.val%cycleLength[g]) - renumber.begin();
if(p.type == 0){ /// �߰�
segtree.update(1, 0, r-1, idx);
}
else{ /// ����
ans[p.idx] += segtree.query(1, 0, r-1, 0, r-1);
}
}
}
void solve(){ /// ������ ó���ϴ� �Լ�
/// �� ���� �ʱ�ȭ
for(int i=1; i<=k; i++){
int x = appleTo[i];
appleList[x].push_back(i);
}
/// Session 1. Ʈ�� -> Ʈ��
for(int i=1; i<=n; i++){
if(inCycle[i] && !child[i].empty()) solveCase1(i);
}
/// Ʈ�� ������ ����Ŭ�� �Ѱ���
for(int i=1; i<=k; i++){
int x = appleTo[i]; ll y = appleDelay[i];
if(inCycle[x]) continue;
y += dist[x], x = cycle[cycleNum[x]][cycleIdx[x]];
appleList[x].push_back(i);
}
/// Session 2. ����Ŭ -> ����Ŭ
for(int i=1; i<=n; i++){
if(inCycle[i] && cycleIdx[i] == 0) solveCase2(i);
}
}
void output(){
for(int i=1; i<=q; i++){
printf("%lld\n", ans[i]);
}
}
Compilation message
harvest.cpp: In function 'void input()':
harvest.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d %d %lld %lld", &n, &k, &L, &C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:30:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
| ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | for(int i=1; i<=k; i++) scanf("%lld", &b[i]);
| ~~~~~^~~~~~~~~~~~~~~
harvest.cpp: In function 'void inputQuery()':
harvest.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
harvest.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | scanf("%d %lld", &p.x, &p.t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
41300 KB |
Output is correct |
| 2 |
Correct |
24 ms |
41656 KB |
Output is correct |
| 3 |
Correct |
26 ms |
42212 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
42244 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
59140 KB |
Output is correct |
| 2 |
Incorrect |
185 ms |
86028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
41300 KB |
Output is correct |
| 2 |
Correct |
24 ms |
41656 KB |
Output is correct |
| 3 |
Correct |
26 ms |
42212 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
42244 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
