//while (clock()<=69*CLOCKS_PER_SEC) #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define shandom_ruffle random_shuffle const int nax=1000*1007; const int n1=(1<<19); int n, m; long long tab[nax]; long long los[nax]; struct drz { long long wag=0; drz *lew=NULL; drz *pra=NULL; drz *zmien(int a, int b, int cel, long long w) { if (a>cel || b<cel) return this; drz *ret=new drz; if (a==b) { ret->wag=w*los[a]; return ret; } ret->lew=lew->zmien(a, (a+b)>>1, cel, w); ret->pra=pra->zmien((a+b+2)>>1, b, cel, w); ret->wag=ret->lew->wag+ret->pra->wag; return ret; } }; drz* start(int a, int b) { drz* ret=new drz; if (a==b) { ret->wag=tab[a]*los[a]; } else { ret->lew=start(a, (a+b)>>1); ret->pra=start((a+b+2)>>1, b); ret->wag=ret->lew->wag+ret->pra->wag; } return ret; } pair <drz*, int> dos[nax]; bool por(drz *a, drz *b) { int graa=1; int grab=n1; while(graa<grab) { if (a->lew->wag!=b->lew->wag) { a=a->lew; b=b->lew; grab=(graa+grab)>>1; } else { a=a->pra; b=b->pra; graa=(graa+grab+2)>>1; } } return ((a->wag)<(b->wag)); } bool mniej(pair <drz*, int> a, pair <drz*, int> b) { if ((a.first->wag)==(b.first->wag)) return a.second<b.second; return por(a.first, b.first); } int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) { scanf("%lld", &tab[i]); los[i]=(rand()%nax)+1; } dos[1]={start(1, n1), 1}; for (int i=2; i<=m; i++) { dos[i].second=i; int p; long long x; scanf("%d%lld", &p, &x); dos[i].first=dos[i-1].first->zmien(1, n1, p, x); } sort(dos+1, dos+1+m, mniej); for (int i=1; i<=m; i++) printf("%d ", dos[i].second); printf("\n"); 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 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | //while (clock()<=69*CLOCKS_PER_SEC) #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define shandom_ruffle random_shuffle const int nax=1000*1007; const int n1=(1<<19); int n, m; long long tab[nax]; long long los[nax]; struct drz { long long wag=0; drz *lew=NULL; drz *pra=NULL; drz *zmien(int a, int b, int cel, long long w) { if (a>cel || b<cel) return this; drz *ret=new drz; if (a==b) { ret->wag=w*los[a]; return ret; } ret->lew=lew->zmien(a, (a+b)>>1, cel, w); ret->pra=pra->zmien((a+b+2)>>1, b, cel, w); ret->wag=ret->lew->wag+ret->pra->wag; return ret; } }; drz* start(int a, int b) { drz* ret=new drz; if (a==b) { ret->wag=tab[a]*los[a]; } else { ret->lew=start(a, (a+b)>>1); ret->pra=start((a+b+2)>>1, b); ret->wag=ret->lew->wag+ret->pra->wag; } return ret; } pair <drz*, int> dos[nax]; bool por(drz *a, drz *b) { int graa=1; int grab=n1; while(graa<grab) { if (a->lew->wag!=b->lew->wag) { a=a->lew; b=b->lew; grab=(graa+grab)>>1; } else { a=a->pra; b=b->pra; graa=(graa+grab+2)>>1; } } return ((a->wag)<(b->wag)); } bool mniej(pair <drz*, int> a, pair <drz*, int> b) { if ((a.first->wag)==(b.first->wag)) return a.second<b.second; return por(a.first, b.first); } int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) { scanf("%lld", &tab[i]); los[i]=(rand()%nax)+1; } dos[1]={start(1, n1), 1}; for (int i=2; i<=m; i++) { dos[i].second=i; int p; long long x; scanf("%d%lld", &p, &x); dos[i].first=dos[i-1].first->zmien(1, n1, p, x); } sort(dos+1, dos+1+m, mniej); for (int i=1; i<=m; i++) printf("%d ", dos[i].second); printf("\n"); return 0; } |