Codeforces Round #393 (Div. 1) (8VC Venture Cup 2017

A. Pavel and barbecue

time limit per test

2 seconds

memory limit per test

256 megabytes

 

Pavel cooks barbecue. There are n skewers, they lay on a brazier in a row, each on one of n positions. Pavel wants each skewer to be cooked some time in every of n positions in two directions: in the one it was directed originally and in the reversed direction.Pavel has a plan: a permutation p and a sequence b1, b2, ..., bn, consisting of zeros and ones. Each second Pavel move skewer on position i to position pi, and if bi equals 1 then he reverses it. So he hope that every skewer will visit every position in both directions.Unfortunately, not every pair of permutation p and sequence b suits Pavel. What is the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements? Note that after changing the permutation should remain a permutation as well.There is no problem for Pavel, if some skewer visits some of the placements several times before he ends to cook. In other words, a permutation p and a sequence b suit him if there is an integer k (k ≥ 2n), so that after k seconds each skewer visits each of the 2nplacements.It can be shown that some suitable pair of permutation p and sequence b exists for any n.

Input

The first line contain the integer n (1 ≤ n ≤ 2·105) — the number of skewers.

The second line contains a sequence of integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the permutation, according to which Pavel wants to move the skewers.

The third line contains a sequence b1, b2, ..., bn consisting of zeros and ones, according to which Pavel wants to reverse the skewers.

Output

Print single integer — the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements.

Examples

input

4
4 3 2 1
0 1 1 1

output

2

input

3
2 3 1
0 0 0

output

1

Note

In the first example Pavel can change the permutation to 4, 3, 1, 2.

In the second example Pavel can change any element of b to 1.

Solution

题意:这道题题意很清真啊...... 题意是有n个炉子。初始有n个正面朝上的烤串。每次把第i炉子上的烤串放到pi的炉子上，如果该炉子的b[i]为1，还需要翻个面。问你最少的改动方法(即改动炉子的p[i]值或改动炉子的b[i]值)使得你的所有烤串可以在所有的炉子都烤过并且最后反面朝上。

解析:首先可以知道,如果∑b[i] %2 的值为偶数,那么是不可能有反面朝上的烤串的,所以如果∑b[i] %2 == 1 , 那么++cnt .

　　考虑这个烤串移动的轨迹最终会形成一个环,如果所有的烤串移动的轨迹在一个环上那么就不需要改动炉子的b[i] 值了,反之,若有tot 个不同的轨迹环, 考虑改动tot个环,每个环向其他环连出一条边,构成一个大环,那么共要改动tot次, cnt+=tot. 最后输出cnt 即可. 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200000;
int p[maxn + 1],b[maxn + 1],n,vis[maxn + 1];
inline void dfs(int x){
    vis[x] = 1;
    if (!vis[p[x]]) dfs(p[x]);
}
int main(){
    scanf("%d",&n);
    for (int i = 1 ; i <= n ; ++i) scanf("%d",&p[i]);
    for (int i = 1 ; i <= n ; ++i) scanf("%d",&b[i]);
    int cnt = 0, ans = 0;
    for (int i = 1 ; i <= n ; ++i) if (b[i] == 1) ++cnt;
    if (cnt%2 == 0) ans = 1;
    cnt = 0;
    memset(vis,0,sizeof(vis));
    for (int i = 1 ; i <= n ; ++i) if (!vis[i]) {
        vis[i] = 1;
        dfs(i);
        ++cnt;
    }
    if (cnt == 1) cout<<ans<<endl;
    else cout<<ans+cnt<<endl;
    return 0;
}

B. Travel Card

time limit per test

2 seconds

memory limit per test

256 megabytes

A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets:

1. a ticket for one trip costs 20 byteland rubles,
2. a ticket for 90 minutes costs 50 byteland rubles,
3. a ticket for one day (1440 minutes) costs 120 byteland rubles.

Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

Input

The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.

Each of the following n lines contains the time of trip ti (0 ≤ ti ≤ 109), measured in minutes from the time of starting the system. All ti are different, given in ascending order, i. e. ti + 1 > ti holds for all 1 ≤ i < n.

Output

Output n integers. For each trip, print the sum the passenger is charged after it.

 

input

3
10
20
30

output

20
20
10

input

10
13
45
46
60
103
115
126
150
256
516

output

20
20
10
0
20
0
0
20
20
10

Note

In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

Solution

题意:就是有3种票,A票花费20元,可以完成一个1分钟de旅行,B票花费50元,可以生效持续90分钟,C票花费120元,可以生效持续一天(1440分钟),然后给出N个旅行的时间,你必须以最优方案买票,要你依次求出完成前i个旅行比前i-1个旅行所多耗费的代价.

题解:莫名其妙就A了......

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000;
int n,t[maxn + 99],f[maxn + 99],p[maxn + 99],ans[maxn + 99],o[maxn + 99];
int main(){
    scanf("%d",&n);
    for (int i = 1 ; i <= n ; ++i) cin>>t[i];
    f[0] = 0;
    int last1440 = 1 , last90 = 1;
    for (int i = 1 ; i <= n ; ++i){
        while (t[i] - t[last1440] + 1> 1440) ++ last1440;
        f[i] = f[last1440 - 1] + 120; p[i] = last1440 - 1; 
        while (t[i] - t[last90] + 1> 90) ++ last90;
        if (f[last90 - 1] + 50 < f[i]){
            f[i] = f[last90 - 1] + 50;
            p[i] =   last90 - 1 ;
        }
        
        if (f[i - 1] + 20 < f[i] ){
            f[i] = f[i - 1] + 20;
            p[i] =   i - 1 ;
        }
    }
   // for (int i = 1 ; i <= n ; ++i) cout<<"p ="<<p[i]<<endl;
   // cout<<endl;
   for (int i = 1 ; i <= n ; ++i) cout<<f[i] - f[i - 1]<<endl;
    return 0;
}

C. Nikita and stack

time limit per test

2 seconds

memory limit per test

256 megabytes

Nikita has a stack. A stack in this problem is a data structure that supports two operations. Operation push(x) puts an integer x on the top of the stack, and operation pop() deletes the top integer from the stack, i. e. the last added. If the stack is empty, then the operation pop() does nothing.

Nikita made m operations with the stack but forgot them. Now Nikita wants to remember them. He remembers them one by one, on the i-th step he remembers an operation he made pi-th. In other words, he remembers the operations in order of some permutation p1, p2, ..., pm. After each step Nikita wants to know what is the integer on the top of the stack after performing the operations he have already remembered, in the corresponding order. Help him!

Input

The first line contains the integer m (1 ≤ m ≤ 105) — the number of operations Nikita made.

The next m lines contain the operations Nikita remembers. The i-th line starts with two integers pi and ti (1 ≤ pi ≤ m, ti = 0 or ti = 1) — the index of operation he remembers on the step i, and the type of the operation. ti equals 0, if the operation is pop(), and 1, is the operation is push(x). If the operation is push(x), the line also contains the integer xi (1 ≤ xi ≤ 106) — the integer added to the stack.

It is guaranteed that each integer from 1 to m is present exactly once among integers pi.

Output

Print m integers. The integer i should equal the number on the top of the stack after performing all the operations Nikita remembered on the steps from 1 to i. If the stack is empty after performing all these operations, print -1.

 

input

2
2 1 2
1 0

output

2
2

input

3
1 1 2
2 1 3
3 0

output

2
3
2

input

5
5 0
4 0
3 1 1
2 1 1
1 1 2

output

-1
-1
-1
-1
2

Note

In the first example, after Nikita remembers the operation on the first step, the operation push(2) is the only operation, so the answer is 2. After he remembers the operation pop() which was done before push(2), answer stays the same.

In the second example, the operations are push(2), push(3) and pop(). Nikita remembers them in the order they were performed.

In the third example Nikita remembers the operations in the reversed order.

Solution

题意:大致是说有个脑残，他忘了自己对一个栈的操作顺序了。现在他只能想起他第几步的操作是什么 （1 : push, 0: pop）。现在问你在他想起来的这前 i 步操做后，栈顶元素是几，栈空输出-1；嗯,就是这样.

题解:我们对于把操作分开看,如果操作是pop(),那么就在数轴上对那个位置-1,否则++;然后动态维护前缀和.对于每次查找,如果我们发现前缀和1~n的值小于0,就输出-1,否则就二分找到前缀和最后一个>0的位置,输出那个位置就可以了,以上操作应该可以用树状数组解决,不过我用了线段树,有时间我再补一个树状数组的程序

线段树:

#include<bits/stdc++.h>
typedef long long LL;  
using namespace std;    
const int maxn = 100000;
int n, step, op, x, ans[maxn + 99];  
struct Node{  int lazy, maxvlaue;}node[maxn*4 ];  
void pushUp(int id, int l, int r){node[id].maxvlaue = max(node[id << 1].maxvlaue, node[id << 1 | 1].maxvlaue);  }  
void pushDown(int id, int l, int r){  
    node[id << 1].lazy += node[id].lazy;  
    node[id << 1 | 1].lazy += node[id].lazy;  
    node[id << 1].maxvlaue += node[id].lazy;  
    node[id << 1 | 1].maxvlaue += node[id].lazy;  
    node[id].lazy = 0;  
}  
void build(int id, int l, int r){  
    if(l == r){  
        node[id].lazy = 0;  
        node[id].maxvlaue = 0;  
        return ;  
    }  
    build(id << 1, l, (l + r) >> 1);  
    build(id << 1 | 1, ((l + r) >> 1)+1, r);  
    node[id].lazy = 0;  
    pushUp(id, l, r);  
}  
void update(int id, int l, int r, int ql, int qr, int p){  
    if(ql == l && qr == r){  
        node[id].lazy += p;  
        node[id].maxvlaue += p;  
        return ;  
    }  
    if(node[id].lazy)   pushDown(id, l, r);  
    if(qr <= (l + r) >> 1)    update(id << 1, l, (l + r) >> 1, ql, qr, p);  
    else if(ql > (l + r) >> 1)  
        update(id << 1 | 1, ((l + r) >> 1) +1, r, ql, qr, p);  
    else{  
        update(id << 1, l, (l + r) >> 1, ql, (l + r) >> 1, p);  
        update(id << 1 | 1, ((l + r) >> 1)+1, r, ((l + r) >> 1)+1, qr, p);  
    }  
    pushUp(id, l, r);  
}  
int query(int id, int l, int r){  
    if(l == r)  return l;  
    if(node[id].lazy)   pushDown(id, l, r);        
    if(node[id << 1 | 1].maxvlaue > 0)  query(id << 1 | 1, ((l + r) >> 1)+1, r);  else  query(id << 1, l, (l + r) >> 1);  
}  
int main(){
    scanf("%d",&n);
    memset(ans,0,sizeof(ans));
    build(1, 1, n);  
    for (int i = 1 ; i <= n ; ++i){  
        scanf("%d%d",&step,&op);
        if(op == 1){  
            scanf("%d",&x);ans[step] = x;  
            update(1, 1, n, 1, step, 1);  
        }  
        else update(1, 1, n, 1, step, -1);               
        if(node[1].maxvlaue > 0){  
            int pos = query(1, 1, n); 
            printf("%d
",ans[pos]); 
        }  
        else printf("-1
");            
    }  
    return 0;  
}  

updating....................