結果
問題 | No.1471 Sort Queries |
ユーザー | chineristAC |
提出日時 | 2021-04-09 21:27:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 16,332 bytes |
コンパイル時間 | 422 ms |
コンパイル使用メモリ | 81,940 KB |
実行使用メモリ | 80,124 KB |
最終ジャッジ日時 | 2024-06-25 04:08:32 |
合計ジャッジ時間 | 4,429 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 52 ms
61,136 KB |
testcase_01 | AC | 51 ms
61,620 KB |
testcase_02 | AC | 52 ms
61,112 KB |
testcase_03 | AC | 58 ms
68,640 KB |
testcase_04 | AC | 52 ms
62,424 KB |
testcase_05 | AC | 51 ms
61,744 KB |
testcase_06 | AC | 50 ms
60,580 KB |
testcase_07 | AC | 50 ms
61,944 KB |
testcase_08 | AC | 62 ms
69,548 KB |
testcase_09 | AC | 55 ms
69,296 KB |
testcase_10 | AC | 51 ms
61,196 KB |
testcase_11 | AC | 51 ms
61,324 KB |
testcase_12 | AC | 57 ms
68,792 KB |
testcase_13 | AC | 82 ms
78,540 KB |
testcase_14 | AC | 82 ms
78,808 KB |
testcase_15 | AC | 86 ms
78,596 KB |
testcase_16 | AC | 81 ms
78,304 KB |
testcase_17 | AC | 82 ms
78,888 KB |
testcase_18 | AC | 80 ms
78,292 KB |
testcase_19 | AC | 81 ms
78,024 KB |
testcase_20 | AC | 86 ms
78,380 KB |
testcase_21 | AC | 85 ms
78,384 KB |
testcase_22 | AC | 83 ms
78,312 KB |
testcase_23 | AC | 93 ms
79,600 KB |
testcase_24 | AC | 94 ms
79,208 KB |
testcase_25 | AC | 93 ms
79,684 KB |
testcase_26 | AC | 91 ms
79,112 KB |
testcase_27 | AC | 95 ms
80,124 KB |
testcase_28 | AC | 94 ms
79,576 KB |
testcase_29 | AC | 92 ms
78,940 KB |
testcase_30 | AC | 90 ms
78,984 KB |
testcase_31 | AC | 96 ms
79,356 KB |
testcase_32 | AC | 95 ms
79,164 KB |
testcase_33 | AC | 97 ms
79,664 KB |
testcase_34 | AC | 98 ms
79,860 KB |
testcase_35 | AC | 98 ms
79,884 KB |
testcase_36 | AC | 98 ms
79,820 KB |
testcase_37 | AC | 96 ms
79,796 KB |
testcase_38 | AC | 91 ms
80,028 KB |
testcase_39 | AC | 90 ms
79,720 KB |
ソースコード
def divisors(M):d=[]i=1while M>=i**2:if M%i==0:d.append(i)if i**2!=M:d.append(M//i)i=i+1return ddef popcount(x):x = x - ((x >> 1) & 0x55555555)x = (x & 0x33333333) + ((x >> 2) & 0x33333333)x = (x + (x >> 4)) & 0x0f0f0f0fx = x + (x >> 8)x = x + (x >> 16)return x & 0x0000007fdef eratosthenes(n):res=[0 for i in range(n+1)]prime=set([])for i in range(2,n+1):if not res[i]:prime.add(i)for j in range(1,n//i+1):res[i*j]=1return primedef factorization(n):res=[]for p in prime:if n%p==0:while n%p==0:n//=pres.append(p)if n!=1:res.append(n)return resdef euler_phi(n):res = nfor x in range(2,n+1):if x ** 2 > n:breakif n%x==0:res = res//x * (x-1)while n%x==0:n //= xif n!=1:res = res//n * (n-1)return resdef ind(b,n):res=0while n%b==0:res+=1n//=breturn resdef isPrimeMR(n):if n==1:return 0d = n - 1d = d // (d & -d)L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]if n in L:return 1for a in L:t = dy = pow(a, t, n)if y == 1: continuewhile y != n - 1:y = (y * y) % nif y == 1 or t == n - 1: return 0t <<= 1return 1def findFactorRho(n):from math import gcdm = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if isPrimeMR(g): return gelif isPrimeMR(n // g): return n // greturn findFactorRho(g)def primeFactor(n):i = 2ret = {}rhoFlg = 0while i*i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += 1 + i % 2if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}return retdef divisors(n):res = [1]prime = primeFactor(n)for p in prime:newres = []for d in res:for j in range(prime[p]+1):newres.append(d*p**j)res = newresres.sort()return resdef xorfactorial(num):#排他的論理和の階乗if num==0:return 0elif num==1:return 1elif num==2:return 3elif num==3:return 0else:x=baseorder(num)return (2**x)*((num-2**x+1)%2)+function(num-2**x)def xorconv(n,X,Y):if n==0:res=[(X[0]*Y[0])%mod]return resx=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]res1=xorconv(n-1,x,y)res2=xorconv(n-1,z,w)former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]former=list(map(lambda x:x%mod,former))latter=list(map(lambda x:x%mod,latter))return former+latterdef merge_sort(A,B):pos_A,pos_B = 0,0n,m = len(A),len(B)res = []while pos_A < n and pos_B < m:a,b = A[pos_A],B[pos_B]if a < b:res.append(a)pos_A += 1else:res.append(b)pos_B += 1res += A[pos_A:]res += B[pos_B:]return resclass UnionFindVerSize():def __init__(self, N):self._parent = [n for n in range(0, N)]self._size = [1] * Nself.group = Ndef find_root(self, x):if self._parent[x] == x: return xself._parent[x] = self.find_root(self._parent[x])stack = [x]while self._parent[stack[-1]]!=stack[-1]:stack.append(self._parent[stack[-1]])for v in stack:self._parent[v] = stack[-1]return self._parent[x]def unite(self, x, y):gx = self.find_root(x)gy = self.find_root(y)if gx == gy: returnself.group -= 1if self._size[gx] < self._size[gy]:self._parent[gx] = gyself._size[gy] += self._size[gx]else:self._parent[gy] = gxself._size[gx] += self._size[gy]def get_size(self, x):return self._size[self.find_root(x)]def is_same_group(self, x, y):return self.find_root(x) == self.find_root(y)class WeightedUnionFind():def __init__(self,N):self.parent = [i for i in range(N)]self.size = [1 for i in range(N)]self.val = [0 for i in range(N)]self.flag = Trueself.edge = [[] for i in range(N)]def dfs(self,v,pv):stack = [(v,pv)]new_parent = self.parent[pv]while stack:v,pv = stack.pop()self.parent[v] = new_parentfor nv,w in self.edge[v]:if nv!=pv:self.val[nv] = self.val[v] + wstack.append((nv,v))def unite(self,x,y,w):if not self.flag:returnif self.parent[x]==self.parent[y]:self.flag = (self.val[x] - self.val[y] == w)returnif self.size[self.parent[x]]>self.size[self.parent[y]]:self.edge[x].append((y,-w))self.edge[y].append((x,w))self.size[x] += self.size[y]self.val[y] = self.val[x] - wself.dfs(y,x)else:self.edge[x].append((y,-w))self.edge[y].append((x,w))self.size[y] += self.size[x]self.val[x] = self.val[y] + wself.dfs(x,y)class Dijkstra():class Edge():def __init__(self, _to, _cost):self.to = _toself.cost = _costdef __init__(self, V):self.G = [[] for i in range(V)]self._E = 0self._V = V@propertydef E(self):return self._E@propertydef V(self):return self._Vdef add_edge(self, _from, _to, _cost):self.G[_from].append(self.Edge(_to, _cost))self._E += 1def shortest_path(self, s):import heapqque = []d = [10**15] * self.Vd[s] = 0heapq.heappush(que, (0, s))while len(que) != 0:cost, v = heapq.heappop(que)if d[v] < cost: continuefor i in range(len(self.G[v])):e = self.G[v][i]if d[e.to] > d[v] + e.cost:d[e.to] = d[v] + e.costheapq.heappush(que, (d[e.to], e.to))return d#Z[i]:length of the longest list starting from S[i] which is also a prefix of S#O(|S|)def Z_algorithm(s):N = len(s)Z_alg = [0]*NZ_alg[0] = Ni = 1j = 0while i < N:while i+j < N and s[j] == s[i+j]:j += 1Z_alg[i] = jif j == 0:i += 1continuek = 1while i+k < N and k + Z_alg[k]<j:Z_alg[i+k] = Z_alg[k]k += 1i += kj -= kreturn Z_algclass BIT():def __init__(self,n,mod=0):self.BIT = [0]*(n+1)self.num = nself.mod = moddef query(self,idx):res_sum = 0mod = self.modwhile idx > 0:res_sum += self.BIT[idx]if mod:res_sum %= modidx -= idx&(-idx)return res_sum#Ai += x O(logN)def update(self,idx,x):mod = self.modwhile idx <= self.num:self.BIT[idx] += xif mod:self.BIT[idx] %= modidx += idx&(-idx)returnclass dancinglink():def __init__(self,n,debug=False):self.n = nself.debug = debugself._left = [i-1 for i in range(n)]self._right = [i+1 for i in range(n)]self.exist = [True for i in range(n)]def pop(self,k):if self.debug:assert self.exist[k]L = self._left[k]R = self._right[k]if L!=-1:if R!=self.n:self._right[L],self._left[R] = R,Lelse:self._right[L] = self.nelif R!=self.n:self._left[R] = -1self.exist[k] = Falsedef left(self,idx,k=1):if self.debug:assert self.exist[idx]res = idxwhile k:res = self._left[res]if res==-1:breakk -= 1return resdef right(self,idx,k=1):if self.debug:assert self.exist[idx]res = idxwhile k:res = self._right[res]if res==self.n:breakk -= 1return resclass SparseTable():def __init__(self,A,merge_func,ide_ele):N=len(A)n=N.bit_length()self.table=[[ide_ele for i in range(n)] for i in range(N)]self.merge_func=merge_funcfor i in range(N):self.table[i][0]=A[i]for j in range(1,n):for i in range(0,N-2**j+1):f=self.table[i][j-1]s=self.table[i+2**(j-1)][j-1]self.table[i][j]=self.merge_func(f,s)def query(self,s,t):b=t-s+1m=b.bit_length()-1return self.merge_func(self.table[s][m],self.table[t-2**m+1][m])class BinaryTrie:class node:def __init__(self,val):self.left = Noneself.right = Noneself.max = valdef __init__(self):self.root = self.node(-10**15)def append(self,key,val):pos = self.rootfor i in range(29,-1,-1):pos.max = max(pos.max,val)if key>>i & 1:if pos.right is None:pos.right = self.node(val)pos = pos.rightelse:pos = pos.rightelse:if pos.left is None:pos.left = self.node(val)pos = pos.leftelse:pos = pos.leftpos.max = max(pos.max,val)def search(self,M,xor):res = -10**15pos = self.rootfor i in range(29,-1,-1):if pos is None:breakif M>>i & 1:if xor>>i & 1:if pos.right:res = max(res,pos.right.max)pos = pos.leftelse:if pos.left:res = max(res,pos.left.max)pos = pos.rightelse:if xor>>i & 1:pos = pos.rightelse:pos = pos.leftif pos:res = max(res,pos.max)return resdef solveequation(edge,ans,n,m):#edge=[[to,dire,id]...]x=[0]*mused=[False]*nfor v in range(n):if used[v]:continuey = dfs(v)if y!=0:return Falsereturn xdef dfs(v):used[v]=Truer=ans[v]for to,dire,id in edge[v]:if used[to]:continuey=dfs(to)if dire==-1:x[id]=yelse:x[id]=-yr+=yreturn rclass Matrix():mod=10**9+7def set_mod(m):Matrix.mod=mdef __init__(self,L):self.row=len(L)self.column=len(L[0])self._matrix=Lfor i in range(self.row):for j in range(self.column):self._matrix[i][j]%=Matrix.moddef __getitem__(self,item):if type(item)==int:raise IndexError("you must specific row and column")elif len(item)!=2:raise IndexError("you must specific row and column")i,j=itemreturn self._matrix[i][j]def __setitem__(self,item,val):if type(item)==int:raise IndexError("you must specific row and column")elif len(item)!=2:raise IndexError("you must specific row and column")i,j=itemself._matrix[i][j]=valdef __add__(self,other):if (self.row,self.column)!=(other.row,other.column):raise SizeError("sizes of matrixes are different")res=[[0 for j in range(self.column)] for i in range(self.row)]for i in range(self.row):for j in range(self.column):res[i][j]=self._matrix[i][j]+other._matrix[i][j]res[i][j]%=Matrix.modreturn Matrix(res)def __sub__(self,other):if (self.row,self.column)!=(other.row,other.column):raise SizeError("sizes of matrixes are different")res=[[0 for j in range(self.column)] for i in range(self.row)]for i in range(self.row):for j in range(self.column):res[i][j]=self._matrix[i][j]-other._matrix[i][j]res[i][j]%=Matrix.modreturn Matrix(res)def __mul__(self,other):if type(other)!=int:if self.column!=other.row:raise SizeError("sizes of matrixes are different")res=[[0 for j in range(other.column)] for i in range(self.row)]for i in range(self.row):for j in range(other.column):temp=0for k in range(self.column):temp+=self._matrix[i][k]*other._matrix[k][j]res[i][j]=temp%Matrix.modreturn Matrix(res)else:n=otherres=[[(n*self._matrix[i][j])%Matrix.mod for j in range(self.column)] for i in range(self.row)]return Matrix(res)def __pow__(self,m):if self.column!=self.row:raise MatrixPowError("the size of row must be the same as that of column")n=self.rowres=Matrix([[int(i==j) for i in range(n)] for j in range(n)])while m:if m%2==1:res=res*selfself=self*selfm//=2return resdef __str__(self):res=[]for i in range(self.row):for j in range(self.column):res.append(str(self._matrix[i][j]))res.append(" ")res.append("\n")res=res[:len(res)-1]return "".join(res)import sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import log,gcdinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N,Q = mi()S = input()cnt = [[0 for j in range(N+1)] for i in range(26)]s = ord("a")for j in range(N):for i in range(26):if S[j]==chr(i+s):cnt[i][j] = 1cnt[i][j] += cnt[i][j-1]ans = []for _ in range(Q):l,r,x = mi()l,r = l-1,r-1for i in range(26):if x > cnt[i][r] - cnt[i][l-1]:x -= cnt[i][r] - cnt[i][l-1]else:ans.append(chr(s+i))breakprint(*ans,sep="\n")