// PA2017, Iloczyn // Andrzej Pezarski #include <cstdio> #include <vector> #include <algorithm> using namespace std; unsigned long long P1 = 22227661796573LL; unsigned long long P2 = 13LL; int N, M, L, I, nodesCnt; struct Node{ int next[2]; unsigned long long val; }; Node *nodes; int *roots; void wczytajT() { for (int i=0; i<N; i++) { int t; scanf("%d", &t); nodes[L+i].val=t; } for (int i=N; i<L; i++) { nodes[L+i].val=0; } for (int v=L-1; v>0; v--) { nodes[v].val = ((nodes[2*v].val*P1)^nodes[2*v+1].val)*P2; nodes[v].next[0]=2*v; nodes[v].next[1]=2*v+1; } roots[0]=1; } int addPath(int v, int p, int x, int l) { l/=2; int newV=nodesCnt++; if (l==0) { nodes[newV].val=x; } else { nodes[newV].next[p<l]=nodes[v].next[p<l]; nodes[newV].next[p>=l]=addPath(nodes[v].next[p>=l], (p<l)?p:(p-l), x, l); nodes[newV].val = ((nodes[nodes[newV].next[0]].val*P1)^nodes[nodes[newV].next[1]].val)*P2; } return newV; } void wczytajM() { for (int m=1; m<M; m++) { int p, x; scanf("%d%d", &p, &x); p--; roots[m]=addPath(roots[m-1], p, x, L); } } bool myCmp(int m1, int m2) { int v1=roots[m1]; int v2=roots[m2]; if (nodes[v1].val==nodes[v2].val) return m1<m2; for (int i=1; i<I; i++) { if (nodes[nodes[v1].next[0]].val==nodes[nodes[v2].next[0]].val) { v1=nodes[v1].next[1]; v2=nodes[v2].next[1]; } else { v1=nodes[v1].next[0]; v2=nodes[v2].next[0]; } } return nodes[v1].val < nodes[v2].val; } int main() { scanf("%d%d", &N, &M); for (L=1, I=1; L<N; L*=2, I++); nodes = new Node[2*L+M*I+10]; roots = new int[M]; nodesCnt=2*L; wczytajT(); wczytajM(); vector<int> res(M); for (int m=0; m<M; m++) { res[m]=m; } // for (int i=0; i<nodesCnt; i++) { // printf("%d %d %d %lld\n", i, nodes[i].next[0], nodes[i].next[1], nodes[i].val); // } sort(res.begin(), res.end(), myCmp); for (auto x:res) printf("%d ", x+1); printf("\n"); delete[] roots; delete[] nodes; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | // PA2017, Iloczyn // Andrzej Pezarski #include <cstdio> #include <vector> #include <algorithm> using namespace std; unsigned long long P1 = 22227661796573LL; unsigned long long P2 = 13LL; int N, M, L, I, nodesCnt; struct Node{ int next[2]; unsigned long long val; }; Node *nodes; int *roots; void wczytajT() { for (int i=0; i<N; i++) { int t; scanf("%d", &t); nodes[L+i].val=t; } for (int i=N; i<L; i++) { nodes[L+i].val=0; } for (int v=L-1; v>0; v--) { nodes[v].val = ((nodes[2*v].val*P1)^nodes[2*v+1].val)*P2; nodes[v].next[0]=2*v; nodes[v].next[1]=2*v+1; } roots[0]=1; } int addPath(int v, int p, int x, int l) { l/=2; int newV=nodesCnt++; if (l==0) { nodes[newV].val=x; } else { nodes[newV].next[p<l]=nodes[v].next[p<l]; nodes[newV].next[p>=l]=addPath(nodes[v].next[p>=l], (p<l)?p:(p-l), x, l); nodes[newV].val = ((nodes[nodes[newV].next[0]].val*P1)^nodes[nodes[newV].next[1]].val)*P2; } return newV; } void wczytajM() { for (int m=1; m<M; m++) { int p, x; scanf("%d%d", &p, &x); p--; roots[m]=addPath(roots[m-1], p, x, L); } } bool myCmp(int m1, int m2) { int v1=roots[m1]; int v2=roots[m2]; if (nodes[v1].val==nodes[v2].val) return m1<m2; for (int i=1; i<I; i++) { if (nodes[nodes[v1].next[0]].val==nodes[nodes[v2].next[0]].val) { v1=nodes[v1].next[1]; v2=nodes[v2].next[1]; } else { v1=nodes[v1].next[0]; v2=nodes[v2].next[0]; } } return nodes[v1].val < nodes[v2].val; } int main() { scanf("%d%d", &N, &M); for (L=1, I=1; L<N; L*=2, I++); nodes = new Node[2*L+M*I+10]; roots = new int[M]; nodesCnt=2*L; wczytajT(); wczytajM(); vector<int> res(M); for (int m=0; m<M; m++) { res[m]=m; } // for (int i=0; i<nodesCnt; i++) { // printf("%d %d %d %lld\n", i, nodes[i].next[0], nodes[i].next[1], nodes[i].val); // } sort(res.begin(), res.end(), myCmp); for (auto x:res) printf("%d ", x+1); printf("\n"); delete[] roots; delete[] nodes; return 0; } |